Sahil has a bag which contains N binary strings. Given a string S and other N-1 strings can be generated by performing right rotations. For example, given N is 2 and S is 10, then the two strings are "10" and "01". You have to find the number of strings which are having an odd decimal equivalent. Help him to find the count of such strings.
INPUT FORMAT :
The first line contains T, the number of test cases.
The first line of each test case contains N the length of the string.
The second line contains binary string S (string of length N).
OUTPUT FORMAT :
For each test case output the count of odd decimal equivalent strings in a newline.
CONSTRAINTS :
1<=T<=100
1<=N<=105
In the test case N = 2
and string is 10
so possible strings are :
10 (decimal equivalent 2)
01(decimal equivalent 1)
so count of odd decimal equivalent is 1.
