CF1527B2 Palindrome Game (hard version)

简单版和困难版的唯一区别在于，简单版中给定的字符串 $s$ 初始时一定是回文串，而困难版则不一定满足这个条件。 回文串是指从左到右和从右到左读都相同的字符串。例如，“101101”是回文串，而“0101”不是。 Alice 和 Bob 正在玩一个关于长度为 $n$ 的字符串 $s$ 的游戏，字符串仅由字符 '0' 和 '1' 组成。两位玩家轮流操作，Alice 先手。 每一回合，玩家可以执行以下两种操作之一： 1. 选择任意 $i$（$1 \le i \le n$），其中 $s[i] = $ '0'，将 $s[i]$ 变为 '1'，并支付 1 美元。 2. 翻转整个字符串，支付 0 美元。该操作仅当当前字符串不是回文串，且上一次操作不是翻转时才允许。也就是说，如果 Alice 翻转了字符串，则 Bob 不能在下一步再次翻转，反之亦然。 翻转字符串指将字符串的字符顺序从最后到第一个重新排列。例如，“01001”翻转后变为“10010”。 当字符串的所有字符都变为 '1' 时，游戏结束。谁在此之前花费的美元最少，谁获胜；如果两人花费相同，则为平局。如果双方都采取最优策略，输出 Alice 获胜、Bob 获胜，还是平局。

第一行包含一个整数 $t$（$1 \le t \le 10^3$），表示测试用例的数量。接下来有 $t$ 组测试数据。 每组测试数据的第一行包含一个整数 $n$（$1 \le n \le 10^3$）。 第二行包含一个长度为 $n$ 的字符串 $s$，仅由字符 '0' 和 '1' 组成。保证字符串 $s$ 至少包含一个 '0'。 注意，所有测试用例中 $n$ 的总和没有限制。

对于每个测试用例，输出一行，仅包含一个单词： - 如果 Alice 获胜，输出 "ALICE"； - 如果 Bob 获胜，输出 "BOB"； - 如果平局，输出 "DRAW"。

在第一个样例中： - 第 $1$ 步，Alice 会选择第 $2$ 种操作翻转字符串，因为如果她选择第 $1$ 种操作必然会输。这也迫使 Bob 必须使用第 $1$ 种操作。 - 第 $2$ 步，Bob 必须执行第 $1$ 种操作，因为不能连续两次翻转。此时所有字符都为 '1'，游戏结束。 Alice 花费 $0$ 美元，Bob 花费 $1$ 美元，因此 Alice 获胜。 在第二个样例中： - 第 $1$ 步，Alice 必须执行第 $1$ 种操作，因为当前字符串是回文串。 - 第 $2$ 步，Bob 翻转字符串。 - 第 $3$ 步，Alice 再次执行第 $1$ 种操作。此时所有字符都为 '1'，游戏结束。 Alice 花费 $2$ 美元，Bob 花费 $0$ 美元，因此 Bob 获胜。 由 ChatGPT 4.1 翻译