Problem Description

After the winter break, Little I returns to school and finds that he has forgotten the password for his bicycle lock. He asks you for help.

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

(An example of a lock where $k = n = 3$, with each column representing a dial, and the positions numbered from top to bottom.)

You can rotate each dial any number of times (or not at all). Each rotation of a dial causes its positions to cycle. Formally, rotating the $j$-th dial once moves the number from the $i$-th position of the $j$-th dial to the $((i \mod k) + 1)$-th position, leaving other dials unchanged.

(An example of rotating the second dial once, transforming the lock from the left to the right.)

For ease of memorization, Little I set the password such that the numbers in each row are as close as possible. Formally, for $1 \leq i \leq k$, the looseness of the $i$-th row of the lock is defined as:

$$ c(i) = \max_{j=1}^n a_{i, j} - \min_{j=1}^n a_{i, j} $$

The looseness of the entire lock is defined as:

$$ C = \max_{1 \leq i \leq k} c(i) $$

Since the unlockable state requires $C$ to be as small as possible, Little I wants you to find the minimum value of $C$.

Input Format

This problem contains multiple test cases, and the problem guarantees that all test cases in a test point have the same $k$.

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

The following are $T$ sets of data, each formatted as follows:

The first line contains a positive integer $n$, representing the number of dials.

The next $k$ lines contain $n$ positive integers each, where the $j$-th integer in the $i$-th line $a_{i,j}$ represents the number on the $i$-th position of the $j$-th dial.

Note that each column in the input matrix corresponds to a dial, not each row.

Output Format

For each set of data, output a line containing an integer representing the minimum value of $C$ among all possible schemes.

Sample Input and Output

Input Sample #1

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

Output Sample #1

0
1

Input Sample #2

See the file in the contestant directory under lock/lock2.in.

Output Sample #2

See the file in the contestant directory under lock/lock2.ans.

Input Sample #3

See the file in the contestant directory under lock/lock3.in.

Output Sample #3

See the file in the contestant directory under lock/lock3.ans.

Input Sample #4

See the file in the contestant directory under lock/lock4.in.

Output Sample #4

See the file in the contestant directory under lock/lock4.ans.

Input Sample #5

See the file in the contestant directory under lock/lock5.in.

Output Sample #5

See the file in the contestant directory under lock/lock5.ans.

Notes/Hints

[Sample 1 Explanation]

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

The following four samples correspond to cases where $k = 1, 2, 3, 4$, respectively, and the values of $n$ have a certain gradient.

[Data Range]

Let $\sum n$ be the sum of $n$ for all test data in a test point.

For all data, it is guaranteed that $1 \leq T$, $1 \leq k \leq 4$, $1 \leq a_{i, j} \leq 3 \times 10^4$.

This problem is divided into two types of test points.

The first type consists of twelve test points, ensuring $k \leq 3$, $n \leq 5 \times 10^4$, $\sum n \leq 1.5 \times 10^5$.

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

[Postscript]

After you have exerted great effort to calculate the value of $C$, Little I tells you that he has already had a locksmith use a hammer to forcefully unlock it. Persuaded by you, Little I promises not to use locks with more than ten thousand dials for locking his bike in the future.

见题面 Input 部分

见题面 Output 部分