Micro's wife Mini gave him a bag having N strings of length N. All the strings are binary i.e. made up of 1's and 0's only. All the strings in the bag can be generated by a string S by simply performing right rotations N times. For example if S is "\(101\)", then the strings in the bag will be "\(110\)", "\(011\)", "\(101\)". Now Mini wants to know the number of ways of selecting one string from the bag with an odd decimal equivalent. Micro got very confused by all this, so he asked for your help.

Input:
The first line consist of an integer T denoting the number of test cases.
First line of each test case consists of an integer denoting N.
Second line of each test case consists of a binary string denoting S.

Ouptut:
Print the answer for each test case in a new line.

Constraints:
\(1 \le T \le 100\)
\(1 \le N \le 10^5 \)