题目描述

小 $\gamma$ 有一个 $n \times m$ 的矩阵 $a$，你需要帮助小 $\gamma$ 进行最少的操作次数使得矩阵每一列都单调不降，对于一次操作：

• 你可以选择矩阵的某一行，并将这一行向左 / 右循环移位一次。

若无解，则输出 $-1$。

注：记矩阵的某一行形成的序列 $a$ 为 $a_1,a_2,a_3,\dots,a_n$，则该序列向左循环移位一格后会变为 $a_2,a_3,\dots,a_n,a_1$，向右循环移位一格后会变为 $a_n,a_1,a_2,a_3,\dots,a_{n-1}$。

输入格式

本题有多组测试数据。

第一行两个非负整数 $c,t$ 分别表示测试点编号和数据组数，特别的，样例 $c = 0$。

对于每组测试数据：

• 第一行输入两个正整数 $n,m$。
• 之后 $n$ 行每行输入 $m$ 个正整数表示矩阵 $a$。

输出格式

对于每组测试数据：

• 若无解，则输出 $-1$，否则输出一个非负整数表示你的答案。

0 6
1 5
3 1 4 1 5
2 3
1 2 3
3 1 2
3 5
1 2 3 4 5
4 5 1 2 3
2 3 4 5 1
3 5
5 4 3 2 1
1 5 4 3 2
2 1 5 4 3
4 5
1 1 1 1 1
2 2 2 2 2
3 3 3 3 3
4 4 4 4 4
2 2
2 2
1 1

0
1
3
2
0
-1

提示

样例解释

对于第一组测试数据，矩阵本身每一列就单调不降了，故输出 $0$ 即可。

对于第二组测试数据，我们可以将矩阵的第二行向左循环移位一次，此时矩阵每一列就单调不降了，可以证明这是最小的操作次数，故输出 $1$ 即可。

对于第三组测试数据，我们可以将矩阵的第二行向左循环移位两次，将矩阵的第三行向右循环移位一次，此时矩阵每一列就单调不降了，可以证明这是最小的操作次数，故输出 $3$ 即可。

数据规模与约定

对于所有数据，保证：

• $1 \le t \le 10$。
• $1 \le n,m \le 300$。
• $1 \le a_{i,j} \le 10^9$。