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.
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$$$.
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.
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
1 5
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: