问题 E: 0 vs 1

Two players named Zero and One are playing a strategic game with a string of characters consisting of only 0s and 1s. 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 1, he lose the game. Similarly, if One picks a 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 ≤ T ≤ 150), denoting the number of test cases. The first line of each test case consists of an integer n (1 ≤ n ≤ 105 ), denoting the length of the string. The second line contains a string of length n consisting of only 0s and 1s, 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.

2
3
110
5
01010

1
-1