SIMPGAME - Divisor Game

no tags 

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, output 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.


hide comments
[Lakshman]: 2015-12-10 20:31:24

2
4
2 10 27 45==>Alice
4
2 10 27 41==>Alice
are above cases are correct?

(reply)=> Yes they are !

(Lakshman)=>I don't know why getting WA is there any corner case which I am missing or my code is completely wrong.

(reply)=> Its completely wrong!

Last edit: 2015-12-11 17:10:39
Akashdeep Goel: 2015-12-08 13:53:07

Nice Problem! :D


Added by:Adarsh kumar
Date:2015-12-07
Time limit:0.200s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:Added by saharshluthra