BG2 - Binary Game Reloaded

no tags 

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

hide comments
anonymous: 2017-04-11 14:08:29

Reverse in this problem means reversing the order of characters. It is _not_ a bit complement.

@wisfaq I understood the problem quite differently. Essentially, as you reverse the substring, other parts still remain unchanged. Thus, the string length remains the same throughout the game. For example, for 00, 01, and 11 we have no valid moves. For 10 we can select whole string and reverse it to get 01.

Last edit: 2017-04-11 21:48:54
wisfaq: 2017-04-11 12:36:21

Only if the input is a one character string Alice can't make a move, so she loses
Otherwise it's always possible to take a one character substring that's the lexicographically smallest substring., and so Bob loses.

Explanation:
for the string 11 she can choose the substring 1, which is lexicographically smaller than 11.
for the string 10 she can choose the substring 0, which is lex.smaller than 10
for the string 01 she can choose the substring 0 which is le,, smaller than01
for the string 00 she can choose the substring 1 which is lex.smaller than 00.
In the same manner we can proceed with longer strings.
As she chooses one character substrings reversion doesn't make any diference.

Last edit: 2017-04-11 21:23:54
Vipul Srivastava: 2017-04-10 14:20:19

In the first case I can understand Bob is the winner as Alice can't make a move but how is the second case winner not Alice. She can choose substring [2,2] and reverse it and the new string will be '00' and Bob can't make a move now.

wisfaq: 2017-04-10 12:02:23

As far as I can see Alice is the winner in all cases.


Added by:BISHAL GAUTAM
Date:2017-04-09
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Big Version of DevSkill Coding Contest-14(https://www.devskill.com/CodingProblems/ViewProblem/282)