题目描述
Kattappa wants Baahubali to master mathematics. They decide to play the following turn-based game.
They will be n x n grid M with random integers. Baahubali begins the game by crossing off an uncrossed row i of the grid. Now it's Kattappa turn and he crosses off an uncrossed column j of the grid. At the end of Kattappa's turn, Baahubali takes the number of candies in the i-th row and j-th column of M, call this value M (i, j), from Kattappa. (If M(i, j) is negative, then Baahubali gives M(i, j) candies to Kattappa.) The game continues alternating turns from Baahubali to Kattappa until the entire board is crossed off. Kattappa wants to know the maximum number of candies that Baahubali can win from him (or the minimum to lose if he cannot win) if both Baahubali and Kattappa play optimally. Help Baahubali find the solution.
Input:
First Line, number of test cases 1 ≤ t ≤ 20
Each test case starts with n (1 ≤ n ≤ 8), 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 maximum number of candies that Baahubali can win from Kattappa. If he cannot win, print the negative number indicating the minimum number of candies he loses.
SAMPLE INPUT
3
2
10 10
-5 -5
2
10 -5
10 -5
2
10 -5
-5 10
SAMPLE OUTPUT
5
5
-10
Explanation
Case 2:
Baahubali selects row 1 (answer doesn't change if row 2 is selected), Kattappa selects second column as -5 is minimum. So the current result is -5.
The only column and row left to be chosen is 10 i.e, second row first column. So the final result is -5 + 10 = 5.
输入格式
见题面
输出格式
见题面