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$.

Input

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.

Output

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.

Examples

Input 1

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

Output 1

0
1

Note

The first test case 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

See lock/lock2.in in the contest directory.

Output 2

See lock/lock2.ans in the contest directory.

Input 3

See lock/lock3.in in the contest directory.

Output 3

See lock/lock3.ans in the contest directory.

Input 4

See lock/lock4.in in the contest directory.

Output 4

See lock/lock4.ans in the contest directory.

Input 5

See lock/lock5.in in the contest directory.

Output 5

See lock/lock5.ans in the contest directory.

Constraints

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$.

Epilogue

After you exerted tremendous effort to compute the value of $C$, Xiao I told you that he had already hired a locksmith to forcibly break it open with a hammer. Under your persistent persuasion, Xiao I promised never to use a combination lock with 10,000 or more dials to lock his bike again.