Alice and Bob always loves to play different games. One day, they were not finding any game to play and so they were feeling disappointed. Suddenly, they found a book in their room with a binary number written onto it, the length of which was not longer than 100000. Then, They formulate the game rule, say "Binary Game".

In this game, the first player chooses a pair of indexes of the binary string and reverses the substring generated by it, so that the string will become lexicographically minimum among all possible selections of indices pairs, and give it to second player. Then, second player do the same thing on the string and give it back to first player. This process continues until there is no way to make binary string lexicographically smaller than before. The player who can not make q move loses the game.

Today, Alice and Bob are playing the Binary Game in their room. Suddenly, you enter into their room. Now, Your task is to determine the winner of the game if both of them play in well disciplined manner and the first player of the game is Alice.

Input

Input starts with an integer T (1<=T<=30), denoting the number of test cases.

Each case contains a binary string probably with leading zeros, which is a binary number in the range of 100000 bit number.

Output

For each case of input, output the name of the winner of the game.

Example

Input:
3
00
01
10

Output:
Bob
Bob
Alice