Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Fivefold Removals

By imAnik · Limits 1s, 1.0 GB

Alice and Bob are playing a simple game on marbles.
They have a bucket containing N marbles, and the rules of the game are as follows:

1. Alice and Bob alter their turns, while Alice makes the first move.
2. Each move consists of removing one or more marbles from the bucket.
3. In the first move, Alice can remove any number of marbles, but not all the marbles in the bucket.
4. In subsequent moves, the current player can remove at most five times the number of marbles removed by the other player in the last move.
5. The player who cannot make a move loses. The other player is considered the winner.
6. Both player plays optimally.

Input

First line of the input contains a single integer t (1 ≤ t ≤ 105) - denoting the number of test cases.
Next t lines each contains a single integer N (1 ≤ N ≤ 1018) - denoting the number of marbles in the bucket.

Output

For each test case, output the winner of the game (Alice or Bob) in a single line.

Sample

InputOutput
8
2
4
6
7
8
10
12
14
Bob
Bob
Bob
Alice
Bob
Bob
Bob
Alice

For N=4, Alice can remove 1 or 2 or 3 marbles in his first move.
Bob removes the remaining marbles in the next move.
Alice cannot make any move and Bob wins.

For N=7, Alice will remove only 1 marble in his first move.
Then Bob can remove maximum 1 × 5 = 5 marbles in his move, but not all the remaining 6.
Alice will remove the remaining marbles in his next move and win.


Discussion

Statistics


25% Solution Ratio

steinumEarliest, 2w ago

steinumFastest, 0.1s

steinumLightest, 655 kB

steinumShortest, 3403B

Submit

Login to submit