Micro and Binary Strings
Tag(s):

## Basic Programming, Bit manipulation, Easy

Problem
Editorial
Analytics

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$

SAMPLE INPUT
1
2
10

SAMPLE OUTPUT
1

Explanation

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

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

HackerEarth Collegiate Cup - First Elimination

OTHER PROBLEMS OF THIS CHALLENGE
• Math > Number Theory
• Algorithms > String Algorithms
• Math > Counting
• Math > Basic Geometry