虽然九条可怜经常出题，但是她发现要一个人出一场比赛是在是太难了，于是她丢下了手头的出题工作开始玩小游戏。

有一个游戏是汉诺塔的改版。在这个游戏中，盘子的大小可以相同，但是保证了相同大小的盘子恰好有 $K$ 个。初始状态下，所有盘子自底向上从大到小地放置在第一根柱子上，对于相同大小的盘子，我们自底向上给它们从 $1$ 到 $K$ 标号。目标是把所有盘子都移动到第三根柱子上。

因为相同大小的盘子的上下顺序没有要求，不难发现合法的终止状态有很多，因此游戏里指定了一种终止状态。游戏的任务是最小化移动的步数。

可怜想了想觉得这个问题好像挺难的，于是她就把这个出到比赛里来给你做啦。

下面给出汉诺塔的具体规则：

• 有三根柱子和若干块圆盘，初始状态下所有圆盘都在第一根柱子上。
• 每一时刻你可以把某一根柱子顶端的圆盘移动到另一根柱子的顶端，目标是把所有盘子都移动到第三根柱子上。
• 移动的过程中必须要保证较大的圆盘不会压在较小的圆盘上。(相同大小的圆盘没有顺序限制)。

输入格式

第一行输入一个整数 $T$ 表示数据组数。

每组数据第一行是两个整数 $n$ 和 $K$。

接下来 $n$ 行按照盘子从大到小的顺序给出终止状态下同一大小的盘子的相对顺序（从左到右依次表示自底向上），例如 $K=2$ 时，$21$ 表示原来在上方的盘子到了下面，原来在下方的盘子到了上面。

输出格式

对于每组数据输出一个整数表示最少步数。

样例一

input

3
3 1
1
1
1
1 2
2 1
4 2
2 1
1 2
1 2
2 1

output

7
2
31

样例二

见样例数据下载。

限制与约定

对于 100% 的数据，保证 $T\le {10}^4,1\le n\le 50,1\le x_i\le K$。

在实际的测试点中，$T$ 组数据的 $K$ 都是相同的。

时间限制：$3\mathtt{\text{s}}$

空间限制：$512\mathtt{\text{MB}}$

下载

样例数据下载