Practice on Toph

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

Easy But Easy Game

By adnan_toky · Limits 2s, 512 MB

Alice and Bob are playing a game on a string ss of length nn consisting of characters ‘0’ and ‘1’. They take alternating turns. Alice moves first.

In each turn, a player selects three different indices ii, jj and kk such that si=0s_i=0, sj=0s_j=0 and sk=1s_k=1 and change sis_i to 11, sjs_j to 11 and sks_k to 00. In other words, the player inverts the characters sis_i, sjs_j and sks_k. The game ends when the string becomes a palindrome or there is no possible move. If the current player has no valid move, he (or she) loses the game.

Who will win the game if both players play optimally?

A palindrome is a string that reads the same backward as forward, for example, strings "0", "010", "10101", "110011" are palindromes, but strings "01", "01101", "1101" are not.

Input

The first line of the input contains a single integer tt (1t1000) (1 \leq t \leq 1000)~- the number of test cases.

The first line of each test case contains an integer n (1n10000) n~ (1 \leq n \leq 10000) ~- the length of the string ss.

The second line of each test case contains the string ss consisting of the characters 00 and 11.

It is guaranteed that the sum of nn over all test cases does not exceed 1000010000.

Output

For each test case, print the answer in a single line.

If Alice wins, print Alice. Otherwise, print Bob.

Sample

InputOutput
5
4
1000
6
100101
8
01001000
4
1001
2
01
Alice
Alice
Bob
Bob
Bob

In the first test case, Alice can select i=2i=2, j=3j=3 and k=1k=1. The string becomes 01100110 after his move which is a palindrome. The game ends after the move and Bob can’t make her move.

In the second test case, Alice can select i=2i=2, j=5j=5 and k=4k=4.

In the third test case, all strategies of Alice lead winning of Bob.

In the fourth test case, Alice can’t move because the string is already palindrome and the game ends before Alice’s move.

In the fifth test case, Alice has no valid move. So, Bob wins.


Discussion

Statistics


14% Solution Ratio

faria_efaEarliest, 2M ago

faria_efaFastest, 0.1s

faria_efaLightest, 402 MB

faria_efaShortest, 2455B

Submit

Login to submit

Editorial

After each move, the number of ones in the string increases by 111. So the game is finite. To solve ...

Related Contests

Toph uses cookies. By continuing you agree to our Cookie Policy.