配点 : $600$ 点

問題文

$T$ 個のテストケースについて、以下の問題を解いてください。

$N$ 個の半開区間 $[L_i,R_i)$ ($1 \le i \le N$) があり、 Alice と Bob がこの区間を使って次のようなゲームをします。

• Alice から始めて、以下の操作を交互に行う。- $N$ 個の区間の中から、既に選ばれているどの区間とも共有点をもたない区間を $1$ つ選ぶ。

先に操作を行えなくなった方が負けで、もう片方のプレイヤーが勝ちます。 双方のプレイヤーが勝利に対して最善を尽くした場合、どちらが勝つことになりますか？

制約

• 入力は全て整数
• $1 \le T \le 20$
• $1 \le N \le 100$
• $1 \le L_i < R_i \le 100$

入力

入力は標準入力から与えられる。入力の $1$ 行目は次の形式である。

$T$

その後、$T$ 個のテストケースが続く。各テストケースは以下の形式で与えられる。

$N$

$L_1$ $R_1$

$L_2$ $R_2$

$\vdots$

$L_N$ $R_N$

出力

計 $T$ 行出力せよ。 そのうち $i$ 行目には、 $i$ 番目のテストケースについて、 Alice が勝つなら Alice 、 Bob が勝つなら Bob と出力せよ。

5
3
53 98
8 43
12 53
10
4 7
5 7
3 7
4 5
5 8
6 9
4 8
5 10
1 9
5 10
2
58 98
11 29
6
79 83
44 83
38 74
49 88
18 45
64 99
1
5 9

Bob
Alice
Bob
Alice
Alice

この入力には、 $5$ つのテストケースが含まれます。

$1$ つ目のテストケースについて、例えば以下のようにゲームが進行します。

• Alice が区間 $[12,53)$ を選択する。
• Bob が区間 $[53,98)$ を選択する。 ゲームに用いる区間は半開区間なので、 $[12,53),[53,98)$ は共有点を持たない。
• Alice はこれ以上操作を行えず、負ける。 Bob はゲームに勝つ。

このテストケースについて、上記の手順が必ずしも両者にとって最善とは限りませんが、両者が最善を尽くした場合勝利するのは Bob であることが示せます。

$2$ つ目のテストケースのように、ひとつのテストケースに同じ区間が複数含まれる場合もあります。