So, one fine day, Shubham was testing his “talent” on our very beloved friend Tuhin!! Being a short-tempered guy, Tuhin quickly got pissed off. So, he decided to teach him a lesson.
He gave him a string of length N, more precisely a “binary string”, consisting of only 0’s and 1’s. He asked him to find all the strings generated from N left rotations one character at a time. For example if S is “101”, then the strings generated from left rotations will be “011”, ”110” and ”101”. Out of the generated N strings, he asks the number of strings having even decimal value.
Help Subham to solve this problem.
The first line consist of an integer T denoting number of test cases. First line of every test case consist of an integer N denoting length of the string and second line of every test cases consist of a binary string S.
Print the answer for every test case in a new line.
After first left rotation the string is “00111”,Similarly the rest strings are “01110”,”11100″,”11001″ and “10011”.
Out of these five strings only two strings “01110” and “11100” have even decimal equivalent.
So the answer is 2.