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 \)
Given binary string : "\(10\)", we need to rotate the string right 2 times.
Rotating Right : "\(01\)", Decimal Equivalent = 1
Rotating Right : "\(10\)", Decimal Equivalent = 2
Clearly there is only one way to select a string having odd decimal equivalent
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor