Matrix is Fun

Input

The first line contains a single integer $t$ (1 \le t \le 10^4) — the number of test cases.

The first line of each test case contains two integers $n$ and $m$ (1 \le n\cdot m \le 2\cdot 10^5) — the number of rows and the number of columns, respectively.

The next $n$ lines each contain $m$ integers M_{i,1}, M_{i,2}, \ldots, M_{i,m} (1 \le M_{i,j} \le n\cdot m). The $i$-th of these lines describes the $i$-th row of the matrix $M$.

It is guaranteed that the sum of n\cdot m over all test cases does not exceed 2\cdot 10^5.

Output

For each test case, output a single integer — the number of columns that can be made perfect after performing any number of upward cyclic shifts.

Examples

Note

In the first test case, no operations are needed: every column of the matrix is already Perfect.

In the second test case, it can be shown that no matter which operations you apply, you cannot make even a single column Perfect.

In the third test case, the entire matrix can be made Perfect using the following operations:

• Cyclically shift column $1$ upwards by $1$:

  \begin{bmatrix} \color{blue}{1} & 2 & 7 & 4 \\ \color{blue}{5} & 6 & 3 & 8 \\ \end{bmatrix}

• Cyclically shift column $3$ upwards by $1$:

  \begin{bmatrix} 1 & 2 & \color{blue}{3} & 4 \\ 5 & 6 & \color{blue}{7} & 8 \\ \end{bmatrix}

Now every element is in its correct position, so the whole matrix is Perfect.

Scoring

1. Subtask $1$ ($50$ points) : (1 \le n,m \le 100)

2. Subtask $2$ ($100$ points) : No additional constraints.