图片被删除,或者路径改变
问题1435--0 vs 1

1435: 0 vs 1

[命题人 : ]
时间限制 : 13.000 sec  内存限制 : 512 MiB

题目描述

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.

输入

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

输出

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

样例输入 Copy

2
3
110
5
01010

样例输出 Copy

1
-1

提示

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.