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

1.Bob plays first and the two players alternate.

2.In his/her turn ,a player can subtract from N any prime number(including 1) less than N.The number thus obtained is the new N.

3.The person who cannot make a move in his/her turn loses the game.

Assuming both play optimally,who wins the game ?

Input format:

The first line contains the number of test cases T.Each of the next lines contains an integer N.

Output format:

Output T lines one for each test case,containing “ALICE” if Alice wins the game ,or “BOB” if Bob wins the game.

Example

Sample Input:
2
1
2

Sample Output:
ALICE
BOB

Constraints:
1 <= T <= 1000000
1 <= N <= 1000000000

Note : For the first test case, Bob cannot make any move and hence Alice wins the game. For the second test case, Bob subtracts 1 from N. Now, Alice cannot make a move and loses the game.

Solution:

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <string.h>

using namespace std;

typedef long long int64;
typedef unsigned long long uint64;
#define two(X) (1<<(X))
#define twoL(X) (((int64)(1))<<(X))
#define contain(S,X) (((S)&two(X))!=0)
#define containL(S,X) (((S)&twoL(X))!=0)
const double pi=acos(-1.0);
const double eps=1e-11;
template<class T> inline void checkmin(T &a,T b){if(b<a) a=b;}
template<class T> inline void checkmax(T &a,T b){if(b>a) a=b;}
template<class T> inline T sqr(T x){return x*x;}
typedef pair<int,int> ipair;
#define SIZE(A) ((int)A.size())
#define LENGTH(A) ((int)A.length())
#define MP(A,B) make_pair(A,B)
#define PB(X) push_back(X)

int main()
{
int testcase,n;
for (scanf(“%d”,&testcase);testcase>0;testcase–)
{
scanf(“%d”,&n);
if ((n&3)==1)
printf(“ALICEn”);
else
printf(“BOBn”);
}
return 0;
}