Although Keliang often sets problems, she found it too difficult to set a contest by herself, so she put aside her problem-setting work and started playing small games.

There is a game that is a variation of the Tower of Hanoi. In this game, disks can have the same size, but it is guaranteed that there are exactly $K$ disks of each size. In the initial state, all disks are placed on the first peg from largest to smallest (bottom to top). For disks of the same size, we label them from $1$ to $K$ from bottom to top. The goal is to move all disks to the third peg.

Since there is no requirement for the vertical order of disks of the same size, it is not difficult to see that there are many valid terminal states, so the game specifies a particular terminal state. The task of the game is to minimize the number of moves.

Keliang thought about it and felt that this problem seemed quite difficult, so she set it in the contest for you to solve.

The specific rules of the Tower of Hanoi are given below:

• There are three pegs and several disks. In the initial state, all disks are on the first peg.
• At any moment, you can move the disk at the top of one peg to the top of another peg. The goal is to move all disks to the third peg.
• During the movement, it must be ensured that a larger disk is never placed on top of a smaller disk. (There is no order restriction for disks of the same size).

Input

The first line contains an integer representing the number of test cases.

For each test case, the first line contains two integers $n$ and $K$.

The next $n$ lines provide the relative order of disks of the same size in the terminal state in order from largest to smallest disk (from left to right represents the order from bottom to top). For example, when $K = 2$, $2\ 1$ means the disk that was originally on top is now at the bottom, and the disk that was originally at the bottom is now on top.

Output

For each test case, output an integer representing the minimum number of moves.

Examples

Input 1

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

Output 1

7
2
31

Constraints

For 100% of the data, it is guaranteed that $T \le 10^4$, $1 \le n \le 50$, and $1 \le x_i \le K$.

In the actual test cases, $K$ is the same for all $T$ test cases.