G. Another GCD Game
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Alice and Bob are playing a game on an array of integers.

They are given an array $$$a$$$ of length $$$n$$$. The players take turns making moves, with Alice moving first.

In a move, the player must select a non-empty subsequence$$$^{\text{∗}}$$$ of the array such that there exists at least one element in the subsequence which is not equal to the $$$\gcd$$$ of all elements in the subsequence.

Let $$$\text{g}$$$ denote the gcd of the selected subsequence. After selecting the subsequence, the player must replace all the elements in the chosen subsequence with the value $$$\text{g}$$$.

More formally, suppose the chosen subsequence corresponds to the indices $$$i_1, i_2, \ldots, i_k$$$. Let $$$$$$ \text{g} = \gcd(a_{i_1}, a_{i_2}, \ldots, a_{i_k}) $$$$$$ The subsequence is valid only if and only if $$$$$$ \exists j \in \{1,2,\ldots,k\} \text{ such that } a_{i_j} \ne \text{g} $$$$$$ After choosing a valid subsequence, set $$$a_{i_j} := \text{g}$$$ for all $$$1 \le j \le k$$$.

The players continue alternating moves on the updated array.

The first player who cannot make a move $$$\color{red}{\text{wins}}$$$.

Assuming both players play optimally, determine who will win the game.

$$$^{\text{∗}}$$$A subsequence is a sequence obtained by deleting zero or more elements from the array without changing the relative order of the remaining elements.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$).

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^{18}$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$.

Output

For each test case, output a single line containing the winner of the game assuming both players play optimally.

Output Alice if Alice wins the game, otherwise output Bob.

Example
Input
3
4
1 1 1 1
2
3 4
3
35 42 30
Output
Alice
Bob
Bob
Note

In the first test case, all elements of the array are equal. For any chosen subsequence, the $$$\gcd$$$ of the subsequence is equal to every element in it, so the condition for a valid move is not satisfied. Hence, no legal move exists for the starting array, and Alice wins the game.

In the second test case, the only valid move for Alice is to select both elements of the array. The $$$\gcd$$$ of the selected subsequence is $$$\gcd(3,4)=1$$$, and since neither of the elements is equal to $$$1$$$, the move is valid. After the move, both elements become $$$1$$$, so the array becomes $$$[1,1]$$$. Now, Bob has no valid move, so Bob wins the game.

In the third test case, it can be shown that Bob wins the game assuming both players play optimally.