After the winter break, Xiao I returned to school and found that he had forgotten the password to his bicycle lock, so he asked for your help.

The combination lock on Xiao I's bicycle has $n$ dials, and each dial has $k$ ($k \le 4$) positions. Each position on the lock contains a positive integer, where the integer at the $i$-th position of the $j$-th dial is $a_{i,j}$.

Figure 4: An example of a lock where $k = n = 3$. Each column represents a dial, and the positions on the dial are numbered from top to bottom.

You can rotate each dial any number of times (including zero). Each rotation shifts the positions of the dial. Formally, rotating the $j$-th dial once moves the number at the $i$-th position of the $j$-th dial to the $((i \pmod k) + 1)$-th position, while other dials remain unchanged.

Figure 5: An example of rotating a dial. Rotating the second dial of the lock on the left once results in the lock on the right.

For easier memorization, Xiao I set the password such that the numbers on the same row are as close as possible. Formally, for $1 \le i \le k$, define the looseness of the $i$-th row of the combination lock as: $$c(i) = \max_{j=1}^{n} a_{i,j} - \min_{j=1}^{n} a_{i,j}$$ Also, define the looseness of the entire combination lock as: $$C = \max_{1 \le i \le k} c(i)$$ Since the state where the lock can be opened requires $C$ to be as small as possible, Xiao I wants you to find the minimum value of $C$.

输入格式

The input is read from the file lock.in.

There are multiple test cases. It is guaranteed that $k$ is the same for all test cases in a single test point.

The first line contains two positive integers $T$ and $k$, representing the number of test cases and the number of positions on each dial, respectively.

Following this are $T$ test cases. The format for each test case is as follows: The first line contains a positive integer $n$, representing the number of dials. The next $k$ lines each contain $n$ positive integers, where the $j$-th integer in the $i$-th line, $a_{i,j}$, represents the number at the $i$-th position of the $j$-th dial.

Note: In the input matrix, each column corresponds to a dial, not each row.

输出格式

The output is written to the file lock.out.

For each test case, output a single line containing an integer representing the minimum value of $C$ among all possible configurations.

样例

Input 1

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

Output 1

0

Note

The first example corresponds to the example in the problem description. After rotating the second dial once, each dial becomes $\{1, 2, 3\}$, and the looseness is 0. It is easy to prove that the looseness cannot be less than 0, so the output is 0.

Input 2

见选手目录下的 lock/lock2.in

Output 2

见选手目录下的 lock/lock2.ans

Input 3

见选手目录下的 lock/lock3.in

Output 3

见选手目录下的 lock/lock3.ans

Input 4

见选手目录下的 lock/lock4.in

Output 4

见选手目录下的 lock/lock4.ans

Input 5

见选手目录下的 lock/lock5.in

Output 5

见选手目录下的 lock/lock5.ans

数据范围

Let $\sum n$ be the sum of $n$ over all test cases in a single test point. For all data, it is guaranteed that $1 \le T$, $1 \le k \le 4$, and $1 \le a_{i,j} \le 3 \times 10^4$.

This problem is divided into two types of test points. The first type consists of twelve test points, where $k \le 3$, $n \le 5 \times 10^4$, and $\sum n \le 1.5 \times 10^5$.

The second type consists of eight test points, where $k = 4$, $n \le 10^4$, and $\sum n \le 3 \times 10^4$.

后记

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