寒假过后，小 I 回到学校，发现自己忘记了自行车锁的密码，于是请你帮忙。

小 I 自行车上的密码锁有 $n$ 个拨圈，每个拨圈有 $k$（$k\le 4$）格。密码锁上的每一格都包含一个正整数，其中第 $j$ 个拨圈的第 $i$ 格上的正整数为 $a_{i,j}$。

一个锁的例子，其中 $k=n=3$，每列表示一个拨圈，拨圈的格子从上往下编号。

你可以对每个拨圈拨若干次（也可以不拨），每拨一次拨圈，它的格子就会进行一次轮换。形式化地，拨第 $j$ 个拨圈一次，则会让第 $j$ 个拨圈上第 $i$ 格的数字移动到第 $((imodk)+1)$ 格，其他拨圈不动。

一个拨动拨圈的例子，对左侧的锁拨一次第二个拨圈得到右侧的锁。

为了方便记忆，小 I 设定密码时要求同一行上的数字尽可能靠近。 形式化地，对于 $1\le i\le k$，定义密码锁第 $i$ 行的松散度为

$$c(i)=\underset{j=1}{\overset{n}{max}}{a}_{i,j}-\underset{j=1}{\overset{n}{min}}{a}_{i,j}$$

同时定义整个密码锁的松散度为

$$C=\underset{1\le i\le k}{max}c(i)$$

因为能开锁的状态满足 $C$ 尽可能小，因此小 I 希望你找出最小的 $C$ 值。

输入格式

本题有多组测试数据，题目保证一个测试点中所有测试数据的 $k$ 相同。

第一行包含两个正整数 $T,k$，分别表示测试数据组数和密码锁拨圈上的格数。

接下来一共 $T$ 组数据，每组数据格式如下：

第一行包含一个正整数 $n$，表示拨圈数。

接下来 $k$ 行，每行包含 $n$ 个正整数，其中第 $i$ 行第 $j$ 个整数 $a_{i,j}$ 表示密码锁第 $j$ 个拨圈上第 $i$ 格对应的数字。

注意输入的矩阵中每一列对应一个拨圈，而非每一行对应一个拨圈。

输出格式

对于每组数据，输出一行包含一个整数，表示所有方案中 $C$ 的最小值。

样例一

input

2 3
3
1 2 1
2 3 2
3 1 3
2
1 2
2 1
1 2

output

0
1

explanation

第一组样例对应题目描述中的例子。

在拨第二个拨圈一次后，每个拨圈都是 $\{1,2,3\}$，此时松散度为 $0$。

容易证明无论如何松散度都不可能小于 $0$，因此输出 $0$。

样例二

见下发文件。

本样例中 $k=1$。

样例三

见下发文件。

本样例中 $k=2$。

样例四

见下发文件。

本样例中 $k=3$。

样例五

见下发文件。

本样例中 $k=4$。

子任务

设 $\sum n$ 为一个测试点中所有测试数据的 $n$ 的和。

对于所有数据，保证 $1\le T$，$1\le k\le 4$，$1\le a_{i,j}\le 3\times {10}^4$。

本题分为两类测试点。

第一类测试点共有十二个，保证 $k\le 3$，$n\le 5\times {10}^4$，$\sum n\le 1.5\times {10}^5$。

第二类测试点共有八个，保证 $k=4$，$n\le {10}^4$， $\sum n\le 3\times {10}^4$。

时间限制：$\cancel{2.5\mathtt{\text{s}}}3.5\mathtt{\text{s}}$

空间限制：$\mathtt{\text{1GB}}$

后记

你花了九牛二虎之力算出 $C$ 的值之后，小 I 却告诉你他已经找开锁师傅用锤子暴力破解了。在你的百般劝说下，小 I 承诺以后锁车不用有大于等于一万个拨圈的密码锁。