K :: ICPC

Time Limit: 2 Seconds    Memory Limit: 32768 KB

Each year the Irregular Creative Pool game Consortium (ICPC) invents a game using pool billiards props and invites all the ICPC members from all over the world to participate and possibly win a plastic trophy.

This year, the game is simple. We have N different balls, numbered from 1 to N. All the balls are in a row in front of the player. The player has to choose one of the balls - called cue ball - and shoot it at the other balls. The cue ball must hit exactly one of the balls - called target ball - on the table (otherwise, the player loses). After the hit, the target ball gets removed from the table, all the balls on the table get rearranged to form a row in front of the table again, and the player continues to choose another ball from table and shoots until there’s only one ball left on the table. The player scores point cumulatively, based on which cue ball hits which target ball.

Assuming a cue ball always hits the target ball and the player will never lose, what is the maximum point a player can get, given the number of balls and the scoring matrix?

Input

The first line of input contains a single integer T (1 ≤ T ≤ 512), which is the number of test cases.

For each test case, the first line contains integer N (2 ≤ N ≤ 10), the number of balls. The next N lines each contain N integers which the jth integer on the ith line is the score for hitting Aj as the target ball with Ai as the cue ball (0 < Aij ≤ 10000).

Output

For each test case, print the maximum points a player can obtain.

Sample Input

2
2
0 1
10 0
3
0 100 1
60 0 1
1 50 0

Sample Output

10
110
Submit

Source: 15th Iran Nationwide Internet Contest