Not Nim

upobir Criterion 2022 Round 18
Limits 1s, 512 MB

Alice and Bob recently learned about Nim. In a Nim game, two players play a game on several stacks of stones. Players alternatively take turns. In a player’s turn, he can choose a non-empty stack and remove some stones from that stack. When a player has no stack to choose from, he or she loses. Now Nim is a classical game and has been studied extensively. So, Alice and Bob tried to change the rules. In their version of the game, after choosing a stack with xx stones, if a player removes yy stones then there should be no number zz such that xyz<xx-y \leq z < x and zz divides xx. Note that since 0 dividing any nonzero number does not make sense, players cannot choose y=xy=x. Happy with the new rules, they start to play. In all games, Alice goes first.

Given the initial description of the game, output who will win given that both play optimally.


First line of the input will contain TT (1T1000001 \le T \le 100000) number of test cases.

Each test case begins with a line containing nn, number of stacks. Next line contains nn space separated numbers, iith number is count of stones in iith stack.


  • Sum of n105n \le 10^5.

  • Count of stones in a stack 2×1018\le 2 \times 10^{18}.


For each test case output who would win in a separate line. If Alice wins, write “Alice”, if Bob wins, write “Bob” without the quotes.


5 6 4
7 7


Login to submit.


13% Solution Ratio
NirjhorEarliest, 1w ago
NirjhorFastest, 0.0s
NirjhorLightest, 131 kB
NirjhorShortest, 540B
Toph uses cookies. By continuing you agree to our Cookie Policy.