问题 E: 0 vs 1

Two players named Zero and One are playing a strategic game with a string of characters consisting of only $\text{0}$s and $\text{1}$s.

The rules of the game are as follows:

• The players take turns removing a single character from either the left or the right end of the string, starting with the player named Zero.
• If Zero picks a $\text{1}$, he lose the game. Similarly, if One picks a $\text{0}$, he loses the game.
• If all characters in the string are removed and no one has lost, the game ends in a draw.

The first line contains a single integer $T$ ($1\le T\le 150$), denoting the number of test cases.

The first line of each test case consists of an integer $n$ (1≤�≤1051≤n≤105), denoting the length of the string.

The second line contains a string of length $n$ consisting of only $\text{0}$s and $\text{1}$s, denoting the initial string of the game.

It is guaranteed that there are no more than $50$ test cases with $n>100$.

2
3
110
5
01010

1
-1