D. Deleting Divisors
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Alice and Bob are playing a game.

They start with a positive integer $n$ and take alternating turns doing operations on it. Each turn a player can subtract from $n$ one of its divisors that isn't $1$ or $n$. The player who cannot make a move on his/her turn loses. Alice always moves first.

Note that they subtract a divisor of the current number in each turn.

You are asked to find out who will win the game if both players play optimally.

Input

The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. Then $t$ test cases follow.

Each test case contains a single integer $n$ ($1 \leq n \leq 10^9$) — the initial number.

Output

For each test case output "Alice" if Alice will win the game or "Bob" if Bob will win, if both players play optimally.

Example
Input
4
1
4
12
69

Output
Bob
Alice
Alice
Bob

Note

In the first test case, the game ends immediately because Alice cannot make a move.

In the second test case, Alice can subtract $2$ making $n = 2$, then Bob cannot make a move so Alice wins.

In the third test case, Alice can subtract $3$ so that $n = 9$. Bob's only move is to subtract $3$ and make $n = 6$. Now, Alice can subtract $3$ again and $n = 3$. Then Bob cannot make a move, so Alice wins.