P9017 [USACO23JAN] Lights Off G

给定正整数 $N$，和两个长为 $N$ 的 $01$ 序列 $a$ 和 $b$。定义一次操作为： 1. 将 $b$ 序列中的一个值翻转（即 $0$ 变成 $1$，$1$ 变成 $0$，下同）。 2. 对于 $b$ 序列中每个值为 $1$ 的位置，将 $a$ 序列中对应位置的值翻转。 3. 将 $b$ 序列向右循环移位 $1$ 位。即若当前 $b$ 序列为 $b_1b_2\cdots b_{n}$，则接下来变为 $b_{n}b_1b_2\cdots b_{n-1}$。 有 $T$ 次询问，对每一次询问，你需要回答出至少需要几次操作，才能使 $a$ 序列中每一个位置的值都变为 $0$。

第一行为两个正整数 $T,N\;(1\leq T\leq 2\times10^5,2\leq N\leq 20)$。 接下来 $T$ 行，每行为两个长为 $N$ 的 $01$ 序列 $a$ 和 $b$，表示一组询问。

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

### 样例一解释 - 第一个测试用例：灯已经全部熄灭。 - 第二个测试用例：我们在第一步中打开第三个开关。 - 第三个测试用例：我们在第一次移动时翻转第一个开关，在第二次移动时扳动第二个开关，然后在第三次移动时再次翻转第二个。 - 第四个测试用例：我们在第一次移动时打开第一个开关，在第二次移动时关闭第三个开关。 可以证明，在每种情况下，这都是所需的最小移动次数。 ### 样例二解释 可以看出，需要2次移动才能关闭所有灯。 - 我们在第一步中打开第七个开关，然后在第二步中再次打开。 数据范围： - 数据点 $3−5$：$N \le 8$ - 数据点 $6−13$：$N \le 18$ - 数据点 $14−20$：无额外约束。