描述

在计算机广泛使用之前，有一种相对方便的数据归档方式，图书管理员将期刊归档在微缩胶片上。微缩胶片是一种矩形卡片，由高分辨率磁性材料制成，可以将报纸页面的图像存储在小至一平方毫米的区域内。可以通过一个具有强大放大能力的设备查看微缩胶片上的报纸。为了保持大量微缩胶片的完好无损并为用户提供良好的检索服务，戈拉姆，一位聪明的图书管理员，发明了一台微缩胶片存储机。

存储机中有n张微缩胶片，每张都有一个独特的编号。机器内有一个目录，可以方便地查找所需微缩胶片的编号。

戈拉姆提出将每张微缩胶片放入一个特殊的框架中，如下图所示。框架的左上角被剪切掉，以确保每张微缩胶片在堆叠时只有一种可能的方向（见下文解释）。

**图1**: 编号为010011的微缩胶片安装在框架上。黑色部分为微缩胶片，白色部分为框架。

微缩胶片的编号通过框架上的二进制编码表示。设g为表示编号所需的位数，编号从0到g-1。框架的左侧包含g个信息单元。信息单元用“1”表示为凹陷，用“0”表示为孔洞。第一个（最上面的）信息单元对应编号的最重要位，最后一个信息单元对应编号的最低位。参考上图。

微缩胶片存储机有三个堆栈，分别是堆栈0、堆栈1和堆栈2，每个堆栈都可以存放n张微缩胶片。如果从上面看这些堆栈，每个堆栈的形状像一个矩形，左上角被剪切。初始时，堆栈0用来存储微缩胶片，堆栈1和堆栈2仅用于执行下面描述的移动操作。该机器还支持更多操作，但此问题中仅考虑“移动”操作。

**图2**: 有一个孔在位置3的微缩胶片被拉出（A），而有凹陷在位置3的则留在堆栈中（B）

操作move(i, k, j): 该操作将所有在信息单元k位置上为“0”的微缩胶片（0 <= k <= g - 1）从堆栈i移动到堆栈j的顶部，保证从堆栈i拉出的微缩胶片的相对顺序与堆栈j中原本的微缩胶片的相对顺序保持不变。实际操作中，将一根棒子插入所有位置k的孔（表示“0”）和凹陷（表示“1”）的槽中。然后，机器将棒子向左拉动，这样在位置k上有孔的微缩胶片（例如图2.A中的微缩胶片）就会被拉出，而位置k上有凹陷的微缩胶片（例如图2.B中的微缩胶片）会留在原地。

戈拉姆希望找到某个特定编号的微缩胶片。为此，他通过执行一系列的移动操作，使得在操作结束后，某个堆栈中只会有他想要的微缩胶片。你的任务是编写一个程序，找到执行此操作所需的最小操作次数。

输入

输入的第一行包含一个整数t（1 <= t <= 10），表示测试用例的个数。接下来的每个测试用例包含以下内容：

• 每个测试用例的第一行包含两个整数n（1 <= n <= 10000）和g（1 <= g <= 15），分别表示微缩胶片的数量和编号的位数。
• 接下来的n行每行包含一个g位的二进制整数，表示一张微缩胶片的编号，不包含前导或尾随空格。测试用例中的第一个微缩胶片为目标微缩胶片。

输出

每个测试用例应输出一行，表示找到目标微缩胶片所需的最小移动次数。

1
4 3
010
011
100
110

2

来源 Tehran 2002 初赛