|Codeforces Round #721 (Div. 2)|
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:
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.
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:
3 3 110 2 00 4 1010
ALICE BOB ALICE
In the first test case of example,
In the second test case of example,