Description

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

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

Input

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

Output

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

2
2 101
1202 110011

2
58