Home

Contest: Task: Related: TaskE TaskG

Score : $600$ points

Problem Statement

Solve the problem below for $T$ test cases.

We have $N$ half-open intervals $[L_i,R_i)$ ($1 \le i \le N$). Using them, Alice and Bob will play the following game:

  • Alice and Bob alternately do the following operation, Alice going first.
    • From the $N$ intervals, choose one that does not intersect with any of the intervals that are already chosen.

The player who gets unable to do the operation loses, and the other player wins.
Which player will win if both players play optimally to win?

What is a half-open interval?A half-open interval $[X,Y)$ is an interval consisting of all real numbers $x$ satisfying $X \leq x < Y$.

Constraints

  • All values in input are integers.
  • $1 \le T \le 20$
  • $1 \le N \le 100$
  • $1 \le L_i < R_i \le 100$

Input

Input is given from Standard Input. The first line is in the following format:

$T$

Then, $T$ test cases follow, each of which is in the following format:

$N$
$L_1$ $R_1$
$L_2$ $R_2$
$\vdots$
$L_N$ $R_N$

Output

Print $T$ lines.
The $i$-th line should contain Alice if Alice wins in the $i$-th test case, and Bob if Bob wins.

Sample Input 1

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

Sample Output 1

Bob
Alice
Bob
Alice
Alice

This input contains five test cases.

For the first test case, we will show one possible progression of the game below.

  • Alice chooses the interval $[12,53)$.
  • Bob chooses the interval $[53,98)$. Note that $[12,53)$ and $[53,98)$ do not intersect since they are half-open.
  • Alice is unable to do an operation, and Bob wins.

These moves may not be the best choices for them, but we can show that Bob will win if both play optimally.

As seen in the second test case, there can be multiple occurrences of the same interval within a test case.