F. A Bit Odd

time limit per test: 3 seconds

memory limit per test: 256 megabytes

input: standard input

output: standard output

Alice and Bob have got a binary^{\text{∗}} string s of length n. They have decided to play a game on it, taking turns alternately, with Alice moving first.

In each move, the player must select a subsequence^{\text{†}} which has an odd number of inversions^{\text{‡}} and delete it. The player who cannot make a move loses.

Determine who wins the game, assuming both players play optimally.

^{\text{∗}}A binary string is a string that consists only of the characters \texttt{0} and \texttt{1}.

^{\text{†}}A sequence a is a subsequence of a string b if a can be obtained from b by the deletion of several (possibly zero or all) characters.

^{\text{‡}}An inversion in a binary string s is a pair of indices (i, j) such that i \lt j and s_i = \texttt{1} and s_j = \texttt{0}.

Input

The first line contains a single integer t (1 \le t \le 10^4) — the number of test cases. Description of each test case follows.

The first line of each test case contains a single integer n (1 \le n \le 2\cdot10^5) — the length of the binary string s.

The second line of each test case contains a binary string s of length n. It is guaranteed that each character of s is either \texttt{0} or \texttt{1}.

It is guaranteed that the sum of n over all the test cases does not exceed 2\cdot10^5.

Output

For each test case, print \texttt{Alice} if Alice wins the game and \texttt{Bob} otherwise.

Example

Input

3

5

10101

4

0100

6

011001

Output

Alice

Alice

Bob

Note

For the first test case, Alice can choose the entire string as it has an odd number of inversions. Now, Bob is left with an empty string, and he cannot make a move. Thus, Alice wins.

For the second test case, Alice can choose the subsequence formed by the characters at indices 1, 2, and 4, i.e., \texttt{010}. Bob is then left with the character at index 3, namely \texttt{0}, which has 0 inversions (an even number). Therefore, Bob cannot choose a subsequence with an odd number of inversions, so Alice wins.

For the third test case, it can be shown that Bob can guarantee a win irrespective of Alice's first move.