C :: Grid Game II

Time Limit: 5 Seconds    Memory Limit: 262144 KB

Atefeh and Behrad both have lots of saffron but want more. They decide to play the following turn-based game.

They fill an n x n grid M with random integers. Atefeh begins the game by crossing off an uncrossed row i of the grid. Now it’s Behrad’s turn and he crosses off an uncrossed column j of the grid. At the end of Behrad’s turn, Atefeh takes the number saffrons in the ith row and jth column of M, call this value M(i, j), from Behrad. (If M(i,j) is negative, then Atefeh gives |M(i, j)| saffron to Behrad.) The game continues alternating turns from Atefeh to Behrad until the entire board is crossed off.

What is the largest amount of saffrons that Atefeh can win from Behrad (or least amount to lose if she cannot win) if both Atefeh and Behrad play optimally? 

The beginning of a game between Atefeh (red) and Behrad (blue).

 

Input

The first line of the input contains an integer t (1 ≤ t ≤ 20), the number of test cases. Each test case starts with n (1 ≤ n ≤ 15), the size of the grid. Then follow n lines containing n numbers separated by spaces describing M. We call the j-th number on i-th line M(i, j) (-1000 ≤ M(i, j)≤ 1000).

 

Output

For each test case, print the largest amount of saffron that Atefeh can win from Behrad. If she cannot win, print the negative number indicating the minimum number of saffron she loses.

 

Sample Input

3
2
10 10
-5 -5
2
10 -5
10 -5
2
10 -5
-5 10

Sample Output

5
5
-10

Submit

Source: 12th Iran Nationwide Internet Contest III