The jar of divisors

http://codeforces.com/gym/100952/problem/G

Alice and Bob play the following game. They choose a number N to play with. The rules are as follows:

- They write each number from 1 to N on a paper and put all these papers in a jar.

- Alice plays first, and the two players alternate.

- In his/her turn, a player can select any available number M and remove its divisors including M.

- The person who cannot make a move in his/her turn wins the game.

Assuming both players play optimally, you are asked the following question: who wins the game?

Input

The first line contains the number of test cases T (1 ≤ T ≤ 20). Each of the next T lines contains an integer (1 ≤ N ≤ 1,000,000,000).

Output

Output T lines, one for each test case, containing Alice if Alice wins the game, or Bob otherwise.

Examples

Input

2
5
1

Output

Alice
Bob

对于这道题其实很简单，题目暗藏玄机，可我一开始的时候也是被骗了，竟然开了10^9的数组，结果发现开不了那么大，
反正神不知鬼不觉的搞了一个多小时，wa了好几次，然后要崩溃了，再仔细看了下题，假设每次都是最优解，我就想是不
是可以重复取，然后就AC了。

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 #include <cmath>
 5 #include <algorithm>
 6 using namespace std;
 7 int main(){
 8     int n;
 9     scanf("%d",&n);
10     while(n--){
11         int m;
12         scanf("%d",&m);
13         if(m>1)
14             printf("Alice
");
15         else
16             printf("Bob
");
17     }
18     return 0;
19 }

2017-07-19