Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

D. Outsmarting
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Alice and Bob play a game with strings.

Each game starts with Alice choosing a string $$$A$$$ of length $$$n$$$ consisting only of the characters 'H' and 'T' and revealing it to Bob.

The rest of the game is played according to the following procedure, in order:

  • Bob chooses a string $$$B$$$ of length $$$n$$$ consisting only of the characters 'H' and 'T', such that $$$A \ne B$$$ and reveals the string to Alice.
  • Now Alice and Bob build a new string $$$S$$$ consisting only of the characters 'H' and 'T'. Bob chooses the first character of $$$S$$$.
  • Then Alice keeps appending a new character ('H' or 'T') to $$$S$$$ until the game ends.

The game ends immediately when one of the following occurs:

  • If $$$A$$$ appears as a substring$$$^{\text{∗}}$$$ of $$$S$$$, then Alice wins.
  • If $$$B$$$ appears as a substring of $$$S$$$, then Bob wins.
  • If the length of $$$S$$$ becomes $$$10^{100}$$$, then Bob wins.

Both players know the rules of the game, and every action is immediately visible to both players.

Now, Alice has already chosen the string $$$A$$$ and revealed it. Given $$$n$$$ and $$$A$$$, determine the winner if both players play optimally from this point onward.

$$$^{\text{∗}}$$$A string $$$a$$$ is a substring of a string $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by deleting several (possibly zero) characters from the beginning and several (possibly zero) characters from the end.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$)  — the number of games. The description of the games follows.

The first line of each game contains a single integer $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$)  — the length of the strings.

The second line contains the string $$$A$$$ of length $$$n$$$, consisting only of the characters 'H' and 'T'  — Alice's chosen string.

It is guaranteed that the sum of $$$n$$$ over all games does not exceed $$$3 \cdot 10^5$$$.

Output

For each game, output a single line containing Alice if Alice wins, and Bob otherwise.

Example
Input
5
2
HT
3
THT
4
TTHT
3
HHH
1
T
Output
Bob
Alice
Alice
Bob
Bob
Note

In the first game, $$$A = {}$$$"HT". Bob can choose $$$B = {}$$$"TH" and set the first character of $$$S$$$ to 'T'. After that, no matter how Alice appends the remaining characters, Bob is guaranteed to win.