CF2004E Not a Nim Problem

Two players, Alice and Bob, are playing a game. They have $ n $ piles of stones, with the $ i $ -th pile initially containing $ a_i $ stones. On their turn, a player can choose any pile of stones and take any positive number of stones from it, with one condition: - let the current number of stones in the pile be $ x $ . It is not allowed to take from the pile a number of stones $ y $ such that the greatest common divisor of $ x $ and $ y $ is not equal to $ 1 $ . The player who cannot make a move loses. Both players play optimally (that is, if a player has a strategy that allows them to win, no matter how the opponent responds, they will win). Alice goes first. Determine who will win.

The first line contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases. Each test case consists of two lines: - the first line contains a single integer $ n $ ( $ 1 \le n \le 3 \cdot 10^5 $ ); - the second line contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 1 \le a_i \le 10^7 $ ). Additional constraint on the input: the sum of $ n $ across all test cases does not exceed $ 3 \cdot 10^5 $ .

For each test case, output Alice if Alice wins, or Bob if Bob wins.