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$.

2
3
110
5
01010

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.