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.