0 vs 1

Problem Description

Two players named Zero and One are playing a strategic game with a string of characters consisting of only $\texttt{0}$s and $\texttt{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 $\texttt{1}$, he lose the game. Similarly, if One picks a $\texttt{0}$, he loses the game. If all characters in the string are removed and no one has lost, the game ends in a draw. If both players are playing optimally, your task is to determine who will win the game, or whether the game will end in a draw.

Input

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\le n\le 10^5$), denoting the length of the string. The second line contains a string of length $n$ consisting of only $\texttt{0}$s and $\texttt{1}$s, denoting the initial string of the game. It is guaranteed that there are no more than $50$ test cases with $n>100$.

Output

For each test case, output a integer in a single line. If One will win the game, output $1$. If Zero will win the game, output $0$. If the game will end in a draw, output $-1$.

Sample Input

2
3
110
5
01010

Sample Output

1
-1

Hint

In the first test case, Zero can only pick up the character 0 from the right in his first turn. Then, it is One's turn to pick up a character. When it comes back to Zero's turn, he can only pick up the character 1, so Zero loses.

Source

2023“钉耙编程”中国大学生算法设计超级联赛（8）