Problem Description

Alice and Bob are playing a game.

They take turns to operate. There are $n$ numbers, $a_1$ , $a_2$ , ... , $a_n$. Every time, the player plays in 3 steps.
1.Arbitrarily chooses one number $a_i$.
2.Arbitrarily chooses another number $x$($1 \leq x < a_i$).
3. Replace the number $a_i$ with $gcd(a_i,x)$. Here, $gcd(u,v)$ refers to the $\textbf{Greatest Common Divisor}$ of $u$ and $v$.

When a player can not make a single move he/she loses the game. Alice moves the first and she asks you to tell her who will win the game if both player play optimally.

Input

The first line contains a number $T$($1 \leq T \leq 100$), the number of testcases.

For each testcase, there are two lines.
The first line contains one number $n$($1 \leq n \leq 10^6$).
The second line contains $n$ numbers $a_1$ , $a_2$ , ... , $a_n$($1 \leq a_i \leq 10^7$).

It is guaranteed that for all testcases, $\sum{n} \leq 10^6$.

Output

For each testcase, output the answer in one line. If Alice will win the game, print "Alice", otherwise print "Bob".

2
1
1
1
2

Bob
Alice