#GYM104679D. Yet Another Mysterious Array
Yet Another Mysterious Array
Description
Alice and Bob went on an adventure, where they found a mysterious array $A$ consisting of $N$ positive integers. The $i$-th element of the array is called $A_i$.
Alice and Bob decided to play a game with this array, where each player moves in turn, and whoever can't find a valid move loses. Alice goes first. In simple words, Alice makes her move, then it is Bob's move, then it is Alice's move again, and so on. In every move, the player (whose move it is) does the following things sequentially:
- Select any prime number $p$ such that there exists an index $i$ such that $p$ divides $A_i$. If no such prime number is found, the player immediately loses.
- For each element $A_j$ from the array, if $p$ divides $A_j$, replace $A_j$ by $\dfrac{A_j}{p}$, else $A_j$ is kept unchanged. (Note that this part should be done for every element of the array, not just one).
- The updated array is passed to the next player.
The first line contains a positive integer representing the number of test cases.
For each test case, the first line contains a positive integer $N$ and the following line contains $N$ space-separated positive integers representing the array $A$.
Constraints
- $1 \leq T \leq 10$
- $1 \leq N \leq 10^5$
- $1 \leq A_i \leq 10^5$
- Sum over $N$ in all test cases will not exceed $10^5$.
For each test case, print "Alice" or "Bob" in a single line without the quotes referring to who will win the game.
Input
The first line contains a positive integer representing the number of test cases.
For each test case, the first line contains a positive integer $N$ and the following line contains $N$ space-separated positive integers representing the array $A$.
Constraints
- $1 \leq T \leq 10$
- $1 \leq N \leq 10^5$
- $1 \leq A_i \leq 10^5$
- Sum over $N$ in all test cases will not exceed $10^5$.
Output
For each test case, print "Alice" or "Bob" in a single line without the quotes referring to who will win the game.
2
4
2 3 2 1
5
727 86197 46727 43969 34157
Bob
Alice
Note
In the first sample test case:
- Alice selects $2$, the array becomes $[1, 3, 1, 1]$.
- Bob selects $3$, the array becomes $[1, 1, 1, 1]$.
- Alice has no move, and Bob wins.