H. Sorting Swim Rings
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are preparing for the opening of the beach season and sorting colorful swim rings. There are $$$n$$$ poles standing vertically from the ground, each with $$$m$$$ swim rings threaded on it in a stack. Each swim ring has one of the colors from $$$1$$$ to $$$n$$$, and every color appears on at least one swim ring. There is also a large area where swim rings can be put temporarily. Initially, this area has no swim ring.

You can perform the operations of moving the swim rings as many times as you like. Each operation is one of the following.

  • Take the top swim ring threaded on a pole and thread it onto the top of another pole.
  • Take the top swim ring threaded on a pole and put it in the temporary area.
  • Choose one swim ring in the temporary area and one of the poles, and thread the swim ring onto the top of that pole.
Since all the swim rings have the same size, the orders of swim rings threaded on the poles never change.

Your goal is to reach a state where all swim rings gathered on each pole have the same color, and the temporary area has no swim ring. You may arbitrarily choose which color of swim rings to gather on which pole. Find the minimum possible number of operations required to reach such a state.

Input

The input contains one or more test cases, each in the following format.

$$$n$$$ $$$m$$$
$$$c_{1,1}$$$ $$$c_{1,2}$$$ $$$\cdots$$$ $$$c_{1,m}$$$
$$$c_{2,1}$$$ $$$c_{2,2}$$$ $$$\cdots$$$ $$$c_{2,m}$$$
$$$\vdots$$$
$$$c_{n,1}$$$ $$$c_{n,2}$$$ $$$\cdots$$$ $$$c_{n,m}$$$

The integer $$$n$$$ represents the number of poles, satisfying $$$2 \le n \le 10$$$. The integer $$$m$$$ represents the number of swim rings initially threaded on each pole, satisfying $$$1 \le m \le 3 \times 10^4$$$.

For each $$$i$$$ and $$$j$$$ ($$$1 \le i \le n$$$, $$$1 \le j \le m$$$), the integer $$$c_{i,j}$$$ represents the color of the $$$j$$$-th swim ring from the bottom on pole $$$i$$$, satisfying $$$1 \le c_{i,j} \le n$$$. In particular, the color of the top swim ring on pole $$$i$$$ is initially $$$c_{i,m}$$$. For each color $$$1, 2, \ldots, n$$$, at least one swim ring of that color appears in the test case.

The end of the input is indicated by a line containing two zeros. The sum of $$$n$$$ over all the test cases does not exceed $$$10$$$.

Output

For each test case, output in a line the minimum possible number of operations.

Example
Input
2 5
2 2 1 1 2
1 1 1 2 2
2 2
1 2
1 1
3 3
1 1 1
1 2 1
3 1 1
0 0
Output
8
3
6
Note

In the first test case of Sample Input 1, first put the top swim ring of pole $$$1$$$ and the top two swim rings of pole $$$2$$$, all of which have color $$$2$$$, in the temporary area. Next, thread the top two swim rings of color $$$1$$$ of pole $$$1$$$ onto the top of pole $$$2$$$. Finally, thread the three swim rings of color $$$2$$$ in the temporary area onto the top of pole $$$1$$$. Then pole $$$1$$$ contains only swim rings of color $$$2$$$, and pole $$$2$$$ contains only swim rings of color $$$1$$$. The number of operations is $$$8$$$, which is the minimum possible.

(1) Initial state
(2) Moving swim rings of color $$$2$$$ to the temporary area
(3) Threading swim rings of color $$$1$$$ onto pole $$$2$$$
(4) Final state
Figure H.1: An example of an optimal sequence of operations in the first test case of Sample Input 1