Searching in sqrt(n) 

In binary, the square root of 2, denoted by sqrt(2), is an infinite number 1.0110101000001001111...

Given an integer n and a binary string (i.e. a string consisting of 0 and 1) S, your task is to find the first occurrence of S in the fraction part (i.e. the part after the decimal point) of sqrt(n). In case sqrt(n) is an integer, the fraction part is an infinite sequence of zeros.

Input 

The first line contains T (T$\le$100), the number of test cases. Each of the following lines contains an integer n ( 2$\le$n$\le$1, 000, 000) and a binary string S with at most 20 characters.

Output 

For each case, print the position of the first character in the first occurrence of S. The first digit after the dot is at position 0. The answer is guaranteed to be no greater than 100.

Sample Input 

2
2 101
1202 110011

Sample Output 

2
58

Problemsetter: Rujia Liu, Special Thanks: Yiming Li, Feng Chen, Jane Alam Jan