Yajilin

Problem Description

You are given a $n\times 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\leq i,j \leq n)$ is $w_{i,j}$. You want to color some cells black, and maximize the sum of weights of these cells.

Input

The first line contains an integer $T(1\leq T\leq 30)$- the number of test cases. For each test case, the first line contains an integer $n(2\leq n\leq 10)$ , each of the following $n$ lines contains $n$ integers $w_{i,j} (0\leq w_{i,j}\leq 10^6)$. The $j$-th number in the $i$-th line indicates the weight of cells in the $i$-th row and the $j$-th column.

Output

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

Sample Input

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

Sample Output

10
28

Source

2020 Multi-University Training Contest 9