6.3 Digit Removal
(RankList for this Question)
Score: 100pts
Time Limit: 1.00 sec
Alice and Bob are bored studying and so want to play a game. They take a random number \(N\). Alice starts playing the game. Each player gets a chance to remove any digit from the number(not necessarily the first or the last digit), the condition being that the sum of the remaining digits in the number is divisible by \(3\). They continue playing until a player cannot make any move or there are no more digits to remove. The player who cannot make a move loses the game. It is given that both players play optimally. Now, you are given the number and you have to output the name of the player who will win this game.

Constraints
\(1 \leq T \leq 10\)
\(1 \leq L \leq 50\)

Input Format
The first line of the input consists of an integer \(T\), denoting the number of test cases.
Each test case has two lines.
The first line of each test case has an integer \(L\), denoting the number of digits in the number.
The second line of the test case contains the number, \(N\).

Output Format
For each test case, output on a new line, the winner of the game.
If the winner is Alice, the print Alice, else, print Bob.

Example 1
Input:
1
3
234

Output:
Alice

Explanation:
Alice can choose the integer 3. Now the remaining digits are 2 and 4, which add up to 6, which is divisible by 3. In the case of Bob, he cannot make any move because if he removes 4, he is left with 2 which is not divisible by 3. Similarly if removes 2, he is left with 4 which is again not divisible by 3.

Example 2
Input:
1
2
30

Output:
Bob

Explanation:
Alice can take any of the two digits available, 3 or 0. In any case, the resulting sum would be divisible by 3. Now, the digit remaining will be either 0 or 3. On removing this digit, there would be no digit left to remove and therefore Alice will not be able to make any move. So Bob would win.

Log In to solve the Question