Given a string $s$ of length $n$ consisting only of '$\texttt{L}$' and '$\texttt{R}$', Alice and Bob intend to play a game using this string.

Alice and Bob take turns operating on the string $s$, with Alice going first.

In each turn, let the current remaining string be $s$. If $s$ is an empty string, the current player loses the game. Otherwise, the player can choose an integer $i$ from $\{1, 2, \cdots, |s|\}$. If $s_i = \texttt{'L'}$, the remaining string after the operation becomes $s_{1}s_{2}\cdots s_{i-1}$. If $s_i = \texttt{'R'}$, the remaining string after the operation becomes $s_{i+1}s_{i+2}\cdots s_{|s|}$.

Both players are perfectly rational and will always adopt the optimal strategy. As an ordinary spectator at PKUWC, you want to determine the winner of this game.

Input

The first line contains a positive integer $T$, representing the number of test cases.

For each test case:

The first line contains a positive integer $n$.

The second line contains a string $s$ of length $n$ consisting only of '$\texttt{L}$' and '$\texttt{R}$', representing the initial string of the game.

Output

For each test case, output a single line containing Alice or Bob, representing the winner of the game.

Examples

Input 1

3
5
LRLLR
6
RLRLRL
1
L

Output 1

Alice
Bob
Alice

Subtasks

Subtask 1 (23 pts): $n\le 10, T\le 20$

Subtask 2 (22 pts): $\sum n\le 500$

Subtask 3 (28 pts): $\sum n\le 5000$

Subtask 4 (27 pts): $\sum n\le 10^6$