Alice and Bob are playing a game. There are n piles having stones. In one move, either player can choose a pile and replace it by two piles, both of which have number of stones more than one and less than the number of stones in the original pile. Moreover, the sizes of both the new piles should be divisors of the size of the original pile. Alice and bob alternate turns and Alice always goes first. The player unable to make a move loses. Assume that both the players play optimally.

Input

the first line contains the number of test cases t.

for each test case, the first line contains the number of piles n.

the next line contain n space separated integers, the sizes of the piles;

Output

For each test case, ouput the name of the winner in a new line.

Constraints

1<=t<=100

1<=n<=1000

1<=size of piles<=100000

Example

Input:
3

1

5

2

3 9

4

4 6 9 10

Output:

Bob

Alice

Bob

Explanation

For the first case, Alice can't replace the pile, so Bob wins.

For the second case, Alice can replace the second pile from 9 to 3,3. Now Bob can't replace any of the piles, so Alice wins.