Description

贝西最近对化学产生了兴趣。目前，她有两种不同颜色的液体，这些液体彼此不易混合。她有两个无限容量的试管，每个试管装满了$N(1 \leq N \leq 10^5)$单位的这两种颜色的液体混合物。因为液体不混合，一旦它们沉淀，就会分成不同颜色的层。因此，这两个试管可以被视为字符串$f_1f_2...f_N$和$s_1s_2...s_N$，其中$f_i$代表第一个试管底部$i$单位处的液体颜色，$s_i$代表第二个试管底部$i$单位处的液体颜色。保证至少有一单位的每种颜色的液体。

贝西想要分离这些液体，使每个试管只包含一种颜色的液体所有单位。她有一个第三个空的、无限容量的烧杯来帮助她完成这项任务。当贝西进行“倒入”操作时，她会将一个试管或烧杯顶部的所有某种颜色的液体移动到另一个容器中。

确定将所有液体分离到两个试管中所需的最少倒入次数，以及完成此操作所需的一系列移动。最终哪个试管装哪种颜色的液体并不重要，但烧杯必须是空的。

将有$T(1 \leq T \leq 10)$个测试案例，每个测试案例有一个参数。 假设将液体分离到原始试管中所需的最少倒入次数为$M$。

• 如果$P=1$，你只需打印$M$。
• 如果$P=2$，你只需打印一个整数$A$，使得$M \leq A \leq M+5$，随后是$A$行构造该解决方案所需的移动数。每行应包含源试管和目标试管的编号（1、2、3对于烧杯）。移动前源试管必须非空，且试管不得自我倒入。
• 如果$P=3$，你需要打印$M$，随后是使用该数量移动的有效构建。

Format

Input

首行包含$T$，即测试案例的数量。对于每个测试案例，下一行包含$N$和$P$，分别代表每个试管最初填充的量和查询类型。接下来的一行包含$f_1f_2...f_N$代表第一个试管。$f_i \in \{1,2\}$且$f_1$代表试管的底部。随后的一行包含$s_1s_2...s_N$代表第二个试管。$s_i \in \{1,2\}$且$s_1$代表试管的底部。

Output

对于每个测试案例，你将打印一个单一的数字，代表分离试管中液体所需的最小倒入次数。

根据查询类型，你可能还需要提供一个有效的构建方案。

Samples

6 
4 1 
1221 
2211 
4 2 
1221 
2211 
4 3 
1221 
2211 
6 3 
222222 
111112 
4 3 
1121 
1222 
4 2 
1121 
1222

4 
4 
1 2 
1 3 
2 1 
3 2 
4 
1 2 
1 3 
2 1 
3 2 
1 
2 1 
5 
2 3 
1 2 
1 3 
1 2 
3 1 
6 
2 3 
1 2 
1 3 
1 2 
2 1 
3 2

Hint

• 输入2-6：P=1
• 输入7-11：P=2
• 输入12-21：没有额外的限制。 另外，保证对于除样本之外的所有输入T=10。

Silver