Problem1025--平方根大搜索

1025: 平方根大搜索

[Creator : ]
Time Limit : 5.000 sec  Memory Limit : 128 MB

Submit

Description

在二进制中,2的算术平方根,即sqrt(2),是一个无限小数1.0110101000001001111...

给定一个整数n和一个01S,你的任务是在sqrt(n)的小数部分(即小数点之后的部分)中找到S第一次出现的位置。如果sqrt(n)是整数,小数部分看作是无限多个0组成的序列。

Input

输入第一行为数据组数T (T<=20)。以下每行为一组数据,仅包含一个整数n (2<=n<=1,000,000)和一个长度不超过20的非空01S。

Output

对于每组数据,输出S的第一次出现中,第一个字符的位置。小数点后的第一个数字的位置为0。输入保证答案不超过100

Sample Input Copy

2
2 101
1202 110011

Sample Output Copy

2
58