Limits
2s, 512 MB

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

In each turn, a player selects three different indices $i$, $j$ and $k$ such that $s_i=0$, $s_j=0$ and $s_k=1$ and change $s_i$ to $1$, $s_j$ to $1$ and $s_k$ to $0$. In other words, the player inverts the characters $s_i$, $s_j$ and $s_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.

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

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

The second line of each test case contains the string $s$ consisting of the characters $0$ and $1$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10000$.

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

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

Input | Output |
---|---|

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=2$, $j=3$ and $k=1$. The string becomes $0110$ 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=2$, $j=5$ and $k=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. |

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