input:

10000
15
010111111011011
10
1000101111
10
0011111101
1
0
3
110
4
1000
8
10000111
20
00000101000100001110
13
1101110110110
13
0111100011010
17
00001001111110101
1
0
20
10001010011000111100
11
00100110101
11
10110101000
15
001011110011000
16
1110111110000111
15
011110110110010
1
0
20
10110001101100010...

output:

7
3
4
0
1
1
2
5
8
5
6
0
7
6
6
5
5
8
0
10
8
7
2
5
0
6
1
3
4
6
7
2
5
1
7
2
1
7
1
4
9
7
7
5
8
11
7
5
3
4
3
1
1
7
7
5
3
0
0
11
7
2
5
5
5
3
6
1
3
5
9
0
2
10
3
3
7
6
3
3
3
2
5
9
4
2
4
3
9
7
7
1
2
3
2
7
10
6
0
0
4
6
3
2
0
4
6
5
1
4
9
2
6
7
6
1
3
6
2
2
3
8
6
1
3
8
7
3
5
4
4
8
3
4
5
3
1
5
6
3
3
0
0
1
1
7
6
4...

result:

wrong answer 1st numbers differ - expected: '11', found: '7'