06708. USACO·关灯 未做

注意：本题的时限为 4 秒，是默认时限的两倍。

Bessie 想睡觉，但农场里的灯让她睡不着。怎样才能把这些灯关掉呢？

Bessie 有两个长度为 $N$（$2\le N\le 20$）的 01 串，分别表示一排灯和一排开关。每盏灯要么开着（1）要么关着（0）；每个开关要么处于激活状态（1）要么处于关闭状态（0）。

一次操作（move）由以下一系列步骤组成：

• 切换恰好一个开关的状态（如果它原本是关闭的，就激活它；反之亦然）。
• 对于每个处于激活状态的开关，切换对应那盏灯的状态（开着就关掉，关着就打开）。
• 将所有开关循环右移一位。具体地说，如果开关对应的 01 串一开始是 $s_0{s}_1\dots s_{N-1}$，那么它会变成 $s_{N-1}{s}_0{s}_1\dots s_{N-2}$。

对于上述问题的 $T$（$1\le T\le 2\cdot 10^5$）组实例，请统计把所有灯都关掉所需的最少操作次数。

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

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

对于每一对，输出把所有灯都关掉所需的最少操作次数。

【样例解释】

可以证明，把所有的灯都关掉需要 $2$ 次操作：第一次操作切换第七个开关，第二次操作再次切换同一个开关。

【数据规模与约定】

• 测试点 3-5：$N\le 8$。

• 测试点 6-13：$N\le 18$。

• 测试点 14-20：无附加限制。