C. Reduce or Divide
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a reverse binary string of a number $$$n$$$.

Alice and Bob are playing a game.

The play starts with the number $$$n$$$. In each turn a player can choose any one of the following moves:

  • Reduce $$$1$$$ from $$$n$$$, if $$$n$$$ is a positive integer.
  • Choose an odd number that is the divisor of $$$n$$$ and greater than $$$1$$$ and divide $$$n$$$ by that number.

The player who is unable to play wins the game.

Bob starts the game. Determine the winner if both Alice and Bob play optimally.

Input

The first line contains a single integer $$$t$$$ $$$(1 \le t \le 10_{}^3)$$$ – the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $$$x$$$ $$$(1 \le x \le 34)$$$ — the length of binary string.

The second line of each test case contains a reverse binary string of $$$n$$$.

Output

For each test case print single world in a new line:

  • "ALICE" if Alice wins the game,
  • "BOB" if Bob wins the game,
  • "DRAW" if the game ends in a draw.

Note that the output is case sensitive.

Example
Input
3
2
11
3
001
3
101
Output
BOB
ALICE
BOB
Note
  • In the first test case, after reversing the string and converting that binary to decimal the number is $$$n = 3$$$. Bob divides $$$n$$$ by $$$3$$$ in the first move. Now $$$n = 1$$$, Alice subtracts $$$1$$$ in the second move. Now $$$n = 0$$$, Bob cannot make a move, so he wins the game.
  • In the second test case, after reversing the string and converting that binary to decimal the number is $$$n = 4$$$. Bob subtracts $$$1$$$ in the first move. Now $$$n = 3$$$, Alice divides $$$n$$$ by $$$3$$$ in the second move. Now $$$n = 1$$$, Bob subtracts $$$1$$$ in the third move. Now $$$n = 0$$$, Alice cannot make a move, so he wins the game.
  • In the third test case, after reversing the string and converting that binary to decimal the number is $$$n = 5$$$. Bob divides $$$n$$$ by $$$5$$$ in the first move. Now $$$n = 1$$$, Alice subtracts $$$1$$$ in the second move. Now $$$n = 0$$$, Bob cannot make a move, so he wins the game.