Description

给定正整数 $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$。

Input Format

第一行为两个正整数 $T,N\;(1\leq T\leq 2\times10^5,2\leq N\leq 20)$。

接下来 $T$ 行，每行为两个长为 $N$ 的 $01$ 序列 $a$ 和 $b$，表示一组询问。

Output Format

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

4 3
000 101
101 100
110 000
111 000

0
1
3
2

1 10
1100010000 1000011000

2

Hint

样例一解释

• 第一个测试用例：灯已经全部熄灭。
• 第二个测试用例：我们在第一步中打开第三个开关。
• 第三个测试用例：我们在第一次移动时翻转第一个开关，在第二次移动时扳动第二个开关，然后在第三次移动时再次翻转第二个。
• 第四个测试用例：我们在第一次移动时打开第一个开关，在第二次移动时关闭第三个开关。 可以证明，在每种情况下，这都是所需的最小移动次数。

样例二解释

可以看出，需要2次移动才能关闭所有灯。

• 我们在第一步中打开第七个开关，然后在第二步中再次打开。

数据范围：

• 数据点 $3−5$：$N \le 8$
• 数据点 $6−13$：$N \le 18$
• 数据点 $14−20$：无额外约束。