Not a Nim Problem
Contest: Educational Codeforces Round 169 (Rated for Div. 2)
Difficulty rating: 2100
Tags: brute force, games, math, number theory

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.

Input format:
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$$$.

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

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Example input:
3
3
3 2 9
4
3 3 6 1
5
1 2 3 4 5

Example output:
Bob
Alice
Bob

Editorial:
So, okay, this is actually a problem related to Nim game and Sprague-Grundy theorem. If you're not familiar with it, I recommend studying it here. The following tutorial expects you to understand how Grundy values are calculated, which you can read there.
The first (naive) solution to this problem would be to calculate the Grundy values for all integers from $$$1$$$ to $$$10^7$$$ via dynamic programming. That would work in $$$O(A^2 log A)$$$ or $$$O(A^2)$$$, where $$$A$$$ is the maximum value in the input, so it's not fast enough.
However, coding a naive solution to this problem might still help. There is a method that allows you to (sometimes) approach these kinds of problems where you can calculate Grundy values slowly, and you need to do it faster. This method usually consists of four steps:
1. code a solution that calculates Grundy values naively;
2. run it and generate several first values of Grundy function;
3. try to observe some patterns and formulate a faster way to calculate Grundy functions using them;
4. verify your patterns on Grundy values of larger numbers and/or try to prove them.
The third step is probably the most difficult, and generating too few Grundy values might lead you to wrong conclusions. For example, the first $$$8$$$ values of Grundy are $$$[1, 0, 2, 0, 3, 0, 4, 0]$$$, which may lead to an assumption that $$$g(x) = 0$$$ if $$$x$$$ is even, or $$$g(x) = \frac{x+1}{2}$$$ if $$$x$$$ is odd. However, this pattern breaks as soon as you calculate $$$g(9)$$$, which is not $$$5$$$, but $$$2$$$. You can pause reading the editorial here and try formulating a different pattern which would explain that; the next paragraph contains the solution.
Okay, we claim that:
• $$$g(1) = 1$$$;
• $$$g(x) = 0$$$ if $$$x$$$ is even;
• $$$g(x) = p(x)$$$ if $$$x$$$ is an odd prime number, where $$$p(x)$$$ is the index of $$$x$$$ in the sequence of prime numbers;
• $$$g(x) = g(d(x))$$$ if $$$x$$$ is an odd composite number, where $$$d(x)$$$ is the minimum prime divisor of $$$x$$$.
We can prove it with induction on $$$x$$$ and something like that:
• $$$g(1) = 1$$$ can simply be verified by calculation;
• if $$$x$$$ is even, there are no transitions to other even values of pile size from the current state of the game (because that would imply that both $$$x$$$ and $$$x-y$$$ are divisible by $$$2$$$, so $$$gcd(x,y)$$$ is at least $$$2$$$). Since these are the only states having Grundy values equal to $$$0$$$, the MEX of all transitions is equal to $$$0$$$;
• if $$$x$$$ is an odd prime number, there are transitions to all states of the game from $$$1$$$ to $$$x-1$$$. The set of Grundy values of these transitions contains all integers from $$$0$$$ to $$$g(x')$$$, where $$$x'$$$ is the previous odd prime number; so, the MEX of this set is $$$g(x') + 1 = p(x') + 1 = p(x)$$$;
• if $$$x$$$ is a composite prime number and $$$d(x)$$$ is its minimum prime divisor, then there are transitions to all states from $$$1$$$ to $$$d(x)-1$$$ (having Grundy values from $$$0$$$ to $$$g(d(x))-1$$$); but every $$$x'$$$ such that $$$g(x') = g(d(x))$$$ is divisible by $$$d(x)$$$; so, there are no transitions to those states (otherwise $$$gcd(x,y)$$$ would be at least $$$d(x)$$$). So, the MEX of all states reachable in one step is $$$g(d(x))$$$.
This is almost the whole solution. However, we need to calculate $$$p(x)$$$ and $$$d(x)$$$ for every $$$x$$$ until $$$10^7$$$. Probably the easiest way to do it is using the linear prime sieve.