Your task is to take an N-by-N matrix and pick numbers that can be added or subtracted from one another to most closely approximate 0. The catch is that you must only use exactly one number in each row and column—no more, no less.

Example

Consider the following matrix where N = 3.

    1   75   10 
   22  500    3
    9  125   50

75 - 22 - 50 = 3 is the correct answer. 10 - 1 - 9 = 0, but 1 and 9 are from the same column. 3 - 1 = 2, but does not use enough numbers.

Input

The first line contains a single positive integer T, representing the number of test cases. T test cases follow. Each test case begins with a line containing a single integer N, representing the size of the matrix. The next N lines each contain N space-separated integers, representing the matrix.

Output

For each test case, output a single line containing the absolute value of the total found that is closest to 0.

Sample

Input
2
2
1 5
4 3
3
1 75 10
22 500 3
9 125 50

Output
1
3