C. Radars
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

We are given a board of size $$$n \times n$$$, where $$$n$$$ is an odd number. For each cell of this board, the cost of building a radar in it is given. The radar covers a square area (with sides parallel to the sides of the board) with a side length of $$$n$$$ and its center in the cell where the radar is located. Your task is to minimize the total cost of building a certain number of radars so that each field of the board is covered at least once. Additionally, you must solve multiple test cases.

Input

The first line of the standard input contains a single integer $$$t$$$ ($$$t \geq 1$$$), indicating the number of test cases.

Then, in $$$t$$$ blocks, the descriptions of subsequent test cases follow.

The first line of the test case description contains a single integer $$$n$$$ ($$$1 \leq n \leq 499; n~\textbf{is odd}$$$), indicating the dimensions of the board.

In the next $$$n$$$ lines, the board description is given.

In the $$$i$$$-th line, there are $$$n$$$ integers $$$a_{i, 1}$$$, $$$a_{i, 2}$$$, ..., $$$a_{i, n}$$$ ($$$1 \leq a_{i, j} \leq 10^9$$$), where $$$a_{i, j}$$$ denotes the cost of building a radar in the cell located in the $$$i$$$-th row and $$$j$$$-th column of the board.

It is guaranteed that the sum of the values of $$$n^2$$$ in one file will not exceed $$$500\,000$$$.

Output

The output should contain $$$t$$$ lines. The $$$i$$$-th line should contain a single integer - the minimum cost of building radars in the $$$i$$$-th test case.

Example
Input
2
3
1 1 1
1 1 1
1 1 1
5
8 5 2 8 3
5 6 9 7 3
7 8 9 1 4
8 9 4 5 5
2 8 6 9 3
Output
1
5
Note

In the first sample test, it is worth building only one radar. In the second, it is worth building three. The optimal positions of the radars along with the areas covered by them are shown in the figures below: