A14341 | Palindrome Game (hard version)

The first line contains a single integer $t$ ( $1 \le t \le 10^3$ ). Then $t$ test cases follow.

The first line of each test case contains a single integer $n$ ( $1 \le n \le 10^3$ ).

The second line of each test case contains the string $s$ of length $n$ , consisting of the characters '0' and '1'. It is guaranteed that the string $s$ contains at least one '0'.

Note that there is no limit on the sum of $n$ over test cases.

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

- "ALICE", if Alice will win the game,
- "BOB", if Bob will win the game,
- "DRAW", if the game ends in a draw.

In the first test case of example,

- in the $1$ -st move, Alice will use the $2$ -nd operation to reverse the string, since doing the $1$ -st operation will result in her loss anyway. This also forces Bob to use the $1$ -st operation.
- in the $2$ -nd move, Bob has to perform the $1$ -st operation, since the $2$ -nd operation cannot be performed twice in a row. All characters of the string are '1', game over.

Alice spends $0$ dollars while Bob spends $1$ dollar. Hence, Alice wins.In the second test case of example,

- in the $1$ -st move Alice has to perform the $1$ -st operation, since the string is currently a palindrome.
- in the $2$ -nd move Bob reverses the string.
- in the $3$ -rd move Alice again has to perform the $1$ -st operation. All characters of the string are '1', game over.

Alice spends $2$ dollars while Bob spends $0$ dollars. Hence, Bob wins.