Easy But Easy Game

adnan_toky Criterion 2022 Round 15
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.


Submit

Login to submit.

Statistics

14% Solution Ratio
faria_efaEarliest, 9M ago
faria_efaFastest, 0.1s
faria_efaLightest, 402 MB
faria_efaShortest, 2455B
Toph uses cookies. By continuing you agree to our Cookie Policy.