SOLVE
LATER
Xsquare loves to play games very much. Today, he has a special square matrix M of size N x N containing both non-negative as well as negative integers which he calls a Gaming Matrix. Rows and columns of his Gaming Matrix are numbered from 1 to N.
In one move, he performs following operations :
NOTE : For a gaming matrix of size N x N where N > 1, Xsquare can select any square matrix of size N-1 as his new gaming matrix which does not contains the discarded cell.
Refer to the figure for better understanding of a gaming move.
Let us consider the following Gaming Matrix of size 3 x 3.
This way Xsquare managed to get a score 24 which is maximum possible score .
Note that Xsquare cannot leave the game in between till it is over.
Your task is very very simple. Given a Gaming Matrix of size N x N. Find the maximum possible score that can be achieved following the above moves .
First line of input contains a single integer T denoting the number of test cases. First line of each test case contains a single integer N denoting the size of the matrix M. Next N line of each test cases contains N space separated integers where j^{th} element in the i^{th} line denotes the value of the cell M[i][j].
For each test case, Print the maximum score that can be achieved from the given gaming matrix .
1 <= T <= 50
1 <= N <= 100
-10^{9} <= M[i][j] <= 10^{9}
Subtask 1 : 1 <= T <= 50 , 1 <= N <= 32 (40 pts)
Subtask 2 : 1 <= T <= 50 , 1 <= N <= 100 (60 pts)
*Problem statement in native language : http://hck.re/z5lNOe *