They take turns to operate. There are n numbers, a1 , a2 , ... , an. Every time, the player plays in 3 steps. 1.Arbitrarily chooses one number ai. 2.Arbitrarily chooses another number x(1≤x<ai). 3. Replace the number ai with gcd(ai,x). Here, gcd(u,v) refers to the Greatest Common Divisor of u and v.
When a player can not make a single move he/she loses the game. Alice moves the first and she asks you to tell her who will win the game if both player play optimally.
Input
The first line contains a number T(1≤T≤100), the number of testcases.
For each testcase, there are two lines. The first line contains one number n(1≤n≤106). The second line contains n numbers a1 , a2 , ... , an(1≤ai≤107).
It is guaranteed that for all testcases, ∑n≤106.
Output
For each testcase, output the answer in one line. If Alice will win the game, print "Alice", otherwise print "Bob".