On his birthday, Perrin received a very unusual puzzle. It consists of an NxN grid of lightbulbs, all of them initially at the off state. The goal is to turn on some of the lights, such that there is exactly one lit bulb in each row, and exactly one lit bulb in each column. Normally this would be an easy exercise, but this puzzle has an additional constraint. For each lightbulb, there is exactly one critical moment of time that the lightbulb can be switched on. As Perrin is a busy man, he does not want to spend a lot of time on the puzzle. Help Perrin calculate the minimum time taken to achieve the goal. Note that the time taken to solve the puzzle is defined as the time difference between the first and the last switching on events.

Input

The first line contains T, the number of test cases. T test cases follow.
The first line of each test case contains a single integer N. N lines follow each containing N integers. The j th integer in the i th of these lines represent the critical time for the bulb in row i, column j.
For any two lightbulbs, the critical times will be different

Output

Output T lines, each with one integer as the answer for the corresponding test case.

Constraints

T <= 100
1 <= N <= 50
0 <= critical times <= 1000000000

Example

Input:
2
2
3 6
9 8
4
10 41 38 66
91 13 95 70
49 32 43 52
51 98 36 19

Output:
3
29

Explanation:

In the first test case, one can either turn on bulbs at times 3 and 8, or at times 6 and 9.Time taken to solve is 5 for the first option and 3 for the second. So the answer is 3.

In the second test case, one optimal way is to turn on lights at times 41,43,51,70.