Bessie 想睡觉，但农场里的灯让她无法入睡。她怎样才能把灯关掉呢？

Bessie 有两个长度为 $N$ ($2\le N\le 20$) 的二进制串，分别表示一列灯和一列开关。每盏灯要么亮着（1），要么熄灭（0）。每个开关要么处于激活状态（1），要么处于未激活状态（0）。

一次行动由以下按顺序进行的操作组成：

1. 恰好切换一个开关的状态（如果未激活，则设为激活，反之亦然）。
2. 对于每个处于激活状态的开关，切换对应灯的状态（如果灯亮着，则将它熄灭，反之亦然）。
3. 将开关向右循环移动一位。具体而言，如果表示开关的二进制串最初为 $s_0s_1\dots s_{N-1}$，则它变为 $s_{N-1}s_0s_1\dots s_{N-2}$。

对于上述问题的 $T$ ($1\le T\le 2\cdot 10^5$) 个实例，求出将所有灯熄灭所需的最少行动次数。

输入格式

第一行包含 $T$ 和 $N$。

接下来 $T$ 行，每行包含一对长度为 $N$ 的二进制串。

输出格式

对于每一对二进制串，输出将所有灯熄灭所需的最少行动次数。

样例

输入格式 1

4 3
000 101
101 100
110 000
111 000

输出格式 1

0
1
3
2

说明

• 第一组测试数据：所有灯已经熄灭。
• 第二组测试数据：我们在第一次行动中切换第三个开关。
• 第三组测试数据：我们在第一次行动中切换第一个开关，在第二次行动中切换第二个开关，在第三次行动中再次切换第二个开关。
• 第四组测试数据：我们在第一次行动中切换第一个开关，在第二次行动中切换第三个开关。

可以证明，每一组中这都是所需的最少行动次数。

输入格式 2

1 10
1100010000 1000011000

输出格式 2

2

说明

可以证明，将所有灯熄灭需要 $2$ 次行动。

• 我们在第一次行动中切换第七个开关，在第二次行动中再次切换它。

子任务

• 测试点 3-5：$N \le 8$
• 测试点 6-13：$N\le 18$
• 测试点 14-20：没有额外限制。

题目作者：William Yue、Eric Yang 和 Benjamin Qi