CF1527B2.Palindrome Game (hard version)

The only difference between the easy and hard versions is that the given string $s$ in the easy version is initially a palindrome, this condition is not always true for the hard version.

A palindrome is a string that reads the same left to right and right to left. For example, "101101" is a palindrome, while "0101" is not.

Alice and Bob are playing a game on a string $s$ of length $n$ consisting of the characters '0' and '1'. Both players take alternate turns with Alice going first.

In each turn, the player can perform one of the following operations:

1. Choose any $i$ ($1 \le i \le n$), where $s[i] =$ '0' and change $s[i]$ to '1'. Pay 1 dollar.
2. Reverse the whole string, pay 0 dollars. This operation is only allowed if the string is currently not a palindrome, and the last operation was not reverse. That is, if Alice reverses the string, then Bob can't reverse in the next move, and vice versa.

Reversing a string means reordering its letters from the last to the first. For example, "01001" becomes "10010" after reversing.

The game ends when every character of string becomes '1'. The player who spends minimum dollars till this point wins the game and it is a draw if both spend equal dollars. If both players play optimally, output whether Alice wins, Bob wins, or if it is a draw.

简单版本与困难版本的唯一区别在于：简单版本中给定的字符串 $s$ 初始时是一个回文串，而困难版本中该条件并不总是成立。

回文串是指从左到右读与从右到左读完全相同的字符串。例如，“101101” 是一个回文串，而 “0101” 则不是。

Alice 和 Bob 在一个长度为 $n$、仅由字符 '0' 和 '1' 构成的字符串 $s$ 上进行一场游戏。两人轮流操作，Alice 先手。

在每一轮中，当前玩家可以执行以下两种操作之一：

1. 选择任意下标 $i$（$1 \le i \le n$），满足 $s[i] =$ '0'，并将 $s[i]$ 改为 '1'；花费 1 美元。
2. 将整个字符串反转，花费 0 美元。该操作仅在当前字符串不是回文串、且上一轮操作不是反转操作时才允许执行。即：若 Alice 执行了反转操作，则 Bob 在下一轮不能反转；反之亦然。

字符串反转是指将其字符顺序倒置（从最后一个字符排到第一个字符）。例如，“01001” 反转后变为 “10010”。

当字符串中所有字符都变为 '1' 时，游戏结束。此时总花费美元数较少的玩家获胜；若双方花费相同，则为平局。若双方均以最优策略进行游戏，请输出 Alice 获胜、Bob 获胜，或平局。

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.

第一行包含一个整数 $t$（$1 \le t \le 10^3$）。随后是 $t$ 组测试数据。

每组测试数据的第一行包含一个整数 $n$（$1 \le n \le 10^3$）。

每组测试数据的第二行包含一个长度为 $n$ 的字符串 $s$，由字符 '0' 和 '1' 组成。保证字符串 $s$ 中至少包含一个 '0'。

注意：所有测试数据的 $n$ 之和没有限制。

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.

对于每个测试用例，在新的一行中输出一个单词：

• 若爱丽丝将赢得游戏，输出 "ALICE"；
• 若鲍勃将赢得游戏，输出 "BOB"；
• 若游戏以平局结束，输出 "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.

在示例的第一个测试用例中：

• 在第 $1$ 步中，Alice 将使用第 $2$ 种操作（翻转字符串），因为若她执行第 $1$ 种操作，则无论如何都会输。这也迫使 Bob 必须使用第 $1$ 种操作。
• 在第 $2$ 步中，Bob 必须执行第 $1$ 种操作，因为第 $2$ 种操作不能连续执行两次。此时字符串所有字符均为 '1'，游戏结束。

Alice 花费了 $0$ 美元，而 Bob 花费了 $1$ 美元。因此，Alice 获胜。

在示例的第二个测试用例中：

• 在第 $1$ 步中，Alice 必须执行第 $1$ 种操作，因为当前字符串本身就是一个回文串。
• 在第 $2$ 步中，Bob 翻转字符串。
• 在第 $3$ 步中，Alice 再次必须执行第 $1$ 种操作。此时字符串所有字符均为 '1'，游戏结束。

Alice 花费了 $2$ 美元，而 Bob 花费了 $0$ 美元。因此，Bob 获胜。