该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给出两个位数均为 $N$ 的二进制数 $a$ 和 $b$ （可能有前导 0 ）。一次操作需要按顺序完成以下三步：

1. 任选 $b$ 的某一位，将该位取反。
2. 对于 $b$ 中每个值为 $1$ 的位，将 $a$ 中对应位的值取反。
3. 将 $b$ 循环右移 $1$ 位。即若当前二进制数 $b$ 为 $b_{N-1} b_{N-2} \cdots b_1 b_0$，则循环右移 1 位后变为 $b_0 b_{N-1} \cdots b_1$。

现在要让 $a$ 经过若干次操作后等于 $0$，则至少需要操作多少次？

多组数据。

输入格式

第一行：两个正整数 $T, N$。其中 $T$ 表示数据组数。

接下来 $T$ 行，每行为两个位数为 $N$ 的二进制数 $a$ 和 $b$。

输出格式

共 $T$ 行，每行一个正整数，表示最少的操作次数。

样例输入 #1

2 3
000 111
101 100

样例输出 #1

0
1

样例输入 #2

3 20
01111101011111001000 01010100101100001010
00001101111100001000 11010111010011101110
10011101100001010100 11111001000001010111

样例输出 #2

7
8
6

数据范围

• 25%的数据满足: $N \le 8$
• 40%的数据满足: $N \le 18$
• 全部的数据满足: $1\leq T\leq 2\times10^5,2\leq N\leq 20$