# 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 $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.

## Input

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$.

## 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=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.

### Statistics

14% Solution Ratio

faria_efaEarliest, 2M ago

faria_efaFastest, 0.1s

faria_efaLightest, 402 MB

faria_efaShortest, 2455B