7597: Yajilin

You are given a n×n rectangular grid of squares. You want to color some cells to black, such that

- Black cells do not touch each other orthogonally(they do not share a side).
- We can draw a single continuous non-intersecting loop that passes through each cell that is not black. The loop must "enter" each cell from the centre of one of its four sides and "exit" from a different side; all turns are 90

degrees.the following is an example

In this problem, the weight of cells (i,j)(1≤i,j≤n) is wi,j . You want to color some cells black, and maximize the sum of weights of these cells.

The first line contains an integer T(1≤T≤30) - the number of test cases.

For each test case, the first line contains an integer n(2≤n≤10) , each of the following n lines contains n integers wi,j(0≤wi,j≤106) . The j -th number in the i -th line indicates the weight of cells in the i -th row and the j -th column

For each test case, output a number - the answer.

2
3
9 8 7
8 8 2
10 4 7
4
7 5 2 4
3 3 5 4
2 2 7 1
8 9 6 8

10
28