Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana

En el sistema binario, la raíz cuadrada de $2$, denotada por $sqrt(2)$, es un número infinito$ 1.0110101000001001111$... 

Dado un entero $n$ y una cadena binaria (los caracteres son $0$ ó $1$) $S$, su tarea consiste en encontrar la primera ocurrencia de $S$ en la parte fraccionaria de $sqrt(n)$. En caso de que $sqrt(n)$ es un entero, la parte fraccionaria es una secuencia infinita de ceros.

Input

La primera línea de la entrada es un entero $T$ $(1 \leq T \leq 100)$ que representa la cantidad de casos de prueba de la entrada. Luego hay $T$ líneas, cada línea contiene un entero $n$ $(2 \leq n \leq 1000000)$ y una cadena binaria $S$, que a lo sumo tiene $20$ caracteres de longitud, separados por un espacio.

Output

Por cada caso de prueba se debe imprimir la posición de la primera ocurrencia de $S$. El primer carácter después del punto es la posición $0$. Se garantiza que la respuesta no es mayor que $140$.

Sample test(s)