3857. [USACO23 Jan Gold] Light Off

【题目描述】

$Bessie$ 想睡觉，但农场的灯光让她睡不着。她怎么能关掉它们？

$Bessie$ 有两个长度为 $N（2≤N≤20）$ 的位串，分别代表灯状态序列和开关状态序列。每个指示灯要么打开（$1$），要么关闭（$0$）。每个开关要么处于激活状态（$1$），要么处于非激活状态（$0$）。

一次 *切换* 由以下 $3$ 步操作组成：

$(1)$只改变一个开关（如果开关处于非活动状态，则将其设置为活动状态，反之亦然）。

$(2)$对于每个激活的开关，改变相应灯的状态（如果灯打开，则将其关闭，反之亦然）。

$(3)$将开关序列循环右移一位。具体而言，如果开关序列最初是：$s_0s_1…s_{N−1}$，则它变为：$s_{N−1}s_0s_1…s_{N–2}$。

对于上述问题的 $T（1≤T≤2·10^5）$ 个样例，计算关闭所有灯所需的最小切换次数。

【输入格式】

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

接下来的 $T$ 行中的每一行包含一对长度为 $N$ 的位串，分别表示灯序列和开关序列的初态。

【输出格式】

对于每组测试数据，输出关闭所有灯所需的最小切换次数。

【样例1输入】

4 3
000 101
101 100
110 000
111 000

【样例1输出】

0
1
3
2

【样例1说明】

第 $1$ 组数据，所有灯都已经关了，无需任何切换操作。

第 $2$ 组数据，需要一次切换：

   在第一次切换中：

       将操作序列由 $100$ 变为 $101$。

       灯的状态由 $101$ 变为 $000$。

       操作序列右移一位变为 $110$。

第 $3$ 组数据：需要三次切换：

   在第一次切换中：

       将操作序列由 $000$ 变为 $100$。

       灯的状态由 $110$ 变为 $010$。

       操作序列右移一位变为 $010$。

   在第二次切换中：

       将操作序列由 $010$ 变为 $000$。

       灯的状态保持 $010$ 不变。

       操作序列右移一位变为 $000$。

   在第三次切换中：

       将操作序列由 $000$ 变为 $010$。

       灯的状态由 $010$ 变为 $000$。

       操作序列右移一位变为 $001$。

第 $4$ 组数据：需要两次切换：

   在第一次切换中：

       将操作序列由 $000$ 变为 $100$。

       灯的状态由 $111$ 变为 $011$。

       操作序列右移一位变为 $010$。

   在第二次切换中：

       将操作序列由 $010$ 变为 $011$。

       灯的状态由 $011$ 变为 $000$。

       操作序列右移一位变为 $101$。

【样例2输入】

1 10
1100010000 1000011000

【样例2输出】

2

【样例2解释】

在第一次切换时，先改变第 $7$ 个开关的状态。

【样例3】

点击下载样例3

【数据规模与约定】

测试点 $3 \sim 5$：$N \leq 8$;

测试点 $6 \sim 13$：$N \leq 18$;

对于 $100\%$ 的数据，$1≤T≤2×10^5,2≤N≤20$;