Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

E. Not a Nim Problem
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Two players, Alice and Bob, are playing a game. They have n piles of stones, with the i-th pile initially containing ai 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

The first line contains a single integer t (1t104) — the number of test cases.

Each test case consists of two lines:

  • the first line contains a single integer n (1n3105);
  • the second line contains n integers a1,a2,,an (1ai107).

Additional constraint on the input: the sum of n across all test cases does not exceed 3105.

Output

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

Example
Input
3
3
3 2 9
4
3 3 6 1
5
1 2 3 4 5
Output
Bob
Alice
Bob