CF1621D.The Winter Hike

Circular land is an $2n \times 2n$ grid. Rows of this grid are numbered by integers from $1$ to $2n$ from top to bottom and columns of this grid are numbered by integers from $1$ to $2n$ from left to right. The cell $(x, y)$ is the cell on the intersection of row $x$ and column $y$ for $1 \leq x \leq 2n$ and $1 \leq y \leq 2n$.

There are $n^2$ of your friends in the top left corner of the grid. That is, in each cell $(x, y)$ with $1 \leq x, y \leq n$ there is exactly one friend. Some of the other cells are covered with snow.

Your friends want to get to the bottom right corner of the grid. For this in each cell $(x, y)$ with $n+1 \leq x, y \leq 2n$ there should be exactly one friend. It doesn't matter in what cell each of friends will be.

You have decided to help your friends to get to the bottom right corner of the grid.

For this, you can give instructions of the following types:

• You select a row $x$. All friends in this row should move to the next cell in this row. That is, friend from the cell $(x, y)$ with $1 \leq y \lt 2n$ will move to the cell $(x, y + 1)$ and friend from the cell $(x, 2n)$ will move to the cell $(x, 1)$.
• You select a row $x$. All friends in this row should move to the previous cell in this row. That is, friend from the cell $(x, y)$ with $1 \lt y \leq 2n$ will move to the cell $(x, y - 1)$ and friend from the cell $(x, 1)$ will move to the cell $(x, 2n)$.
• You select a column $y$. All friends in this column should move to the next cell in this column. That is, friend from the cell $(x, y)$ with $1 \leq x \lt 2n$ will move to the cell $(x + 1, y)$ and friend from the cell $(2n, y)$ will move to the cell $(1, y)$.
• You select a column $y$. All friends in this column should move to the previous cell in this column. That is, friend from the cell $(x, y)$ with $1 \lt x \leq 2n$ will move to the cell $(x - 1, y)$ and friend from the cell $(1, y)$ will move to the cell $(2n, y)$.

Note how friends on the grid border behave in these instructions.

Example of applying the third operation to the second column. Here, colorful circles denote your friends and blue cells are covered with snow.

You can give such instructions any number of times. You can give instructions of different types. If after any instruction one of your friends is in the cell covered with snow he becomes ill.

In order to save your friends you can remove snow from some cells before giving the first instruction:

• You can select the cell $(x, y)$ that is covered with snow now and remove snow from this cell for $c_{x, y}$ coins.

You can do this operation any number of times.

You want to spend the minimal number of coins and give some instructions to your friends. After this, all your friends should be in the bottom right corner of the grid and none of them should be ill.

Please, find how many coins you will spend.

环形土地是一个 $2n \times 2n$ 的网格。该网格的行从上到下依次编号为 $1$ 到 $2n$，列从左到右依次编号为 $1$ 到 $2n$。单元格 $(x, y)$ 表示第 $x$ 行与第 $y$ 列相交处的单元格，其中 $1 \leq x \leq 2n$ 且 $1 \leq y \leq 2n$。

你的 $n^2$ 位朋友全部位于网格的左上角区域：即对所有满足 $1 \leq x, y \leq n$ 的单元格 $(x, y)$，每个单元格中恰好有一位朋友。其余某些单元格被积雪覆盖。

你的朋友们希望到达网格的右下角区域。为此，需确保每个满足 $n+1 \leq x, y \leq 2n$ 的单元格 $(x, y)$ 中恰好有一位朋友（朋友在右下角区域内的具体分布位置不限）。

你决定帮助朋友们抵达网格右下角区域。

为此，你可以发出如下四种类型的指令：

• 选定某一行 $x$：该行中所有朋友均向右移动一格。即，位于单元格 $(x, y)$ 的朋友（其中 $1 \leq y < 2n$）将移至 $(x, y + 1)$；而位于 $(x, 2n)$ 的朋友将移至 $(x, 1)$。
• 选定某一行 $x$：该行中所有朋友均向左移动一格。即，位于单元格 $(x, y)$ 的朋友（其中 $1 < y \leq 2n$）将移至 $(x, y - 1)$；而位于 $(x, 1)$ 的朋友将移至 $(x, 2n)$。
• 选定某一列 $y$：该列中所有朋友均向下移动一格。即，位于单元格 $(x, y)$ 的朋友（其中 $1 \leq x < 2n$）将移至 $(x + 1, y)$；而位于 $(2n, y)$ 的朋友将移至 $(1, y)$。
• 选定某一列 $y$：该列中所有朋友均向上移动一格。即，位于单元格 $(x, y)$ 的朋友（其中 $1 < x \leq 2n$）将移至 $(x - 1, y)$；而位于 $(1, y)$ 的朋友将移至 $(2n, y)$。

注意：上述指令中，位于网格边界的朋友们将按“环形”方式移动（即移出边界后从对侧进入）。

对第二列执行第三种操作（向下移动）的示例图。图中彩色圆圈代表你的朋友，蓝色单元格表示被积雪覆盖的单元格。

你可以任意多次发出上述指令，也可以混合使用不同类型的指令。若在任意一次指令执行后，有朋友处于被积雪覆盖的单元格中，则该朋友将生病。

为保护朋友们，你可在发出第一条指令前清除部分单元格的积雪：

• 你可以选定一个当前被积雪覆盖的单元格 $(x, y)$，并花费 $c_{x, y}$ 枚金币将其积雪清除。

该操作可执行任意多次。

你的目标是以最少的金币花费，发出一系列指令，使得最终所有朋友均位于网格右下角区域（即所有满足 $n+1 \leq x, y \leq 2n$ 的单元格中各恰有一位朋友），且无任何人因积雪而生病。

请计算你所需花费的最少金币数。

The first line contains a single integer $t$ ($1 \leq t \leq 100$) — the number of test cases.

The first line of each test case contains the single integer $n$ ($1 \leq n \leq 250$).

Each of the next $2n$ lines contains $2n$ integers $c_{i, 1}, c_{i, 2}, \ldots, c_{i, 2n}$ ($0 \leq c_{i, j} \leq 10^9$) — costs of removing snow from cells. If $c_{i, j} = 0$ for some $i, j$ than there is no snow in cell $(i, j)$. Otherwise, cell $(i, j)$ is covered with snow.

It is guaranteed that $c_{i, j} = 0$ for $1 \leq i, j \leq n$.

It is guaranteed that the sum of $n$ over all test cases doesn't exceed $250$.

第一行包含一个整数 $t$（$1 \leq t \leq 100$）—— 测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 250$）。

接下来的 $2n$ 行中，每行包含 $2n$ 个整数 $c_{i, 1}, c_{i, 2}, \ldots, c_{i, 2n}$（$0 \leq c_{i, j} \leq 10^9$）—— 清除各单元格积雪的费用。若对某些 $i, j$ 有 $c_{i, j} = 0$，则单元格 $(i, j)$ 中无积雪；否则，单元格 $(i, j)$ 被积雪覆盖。

保证对所有满足 $1 \leq i, j \leq n$ 的 $i, j$，均有 $c_{i, j} = 0$。

保证所有测试用例的 $n$ 值之和不超过 $250$。

For each test case output one integer — the minimal number of coins you should spend.

对于每个测试用例，输出一个整数——你需要花费的最少硬币数量。

In the first test case you can remove snow from the cells $(2, 1)$ and $(2, 2)$ for $100$ coins. Then you can give instructions

• All friends in the first collum should move to the previous cell. After this, your friend will be in the cell $(2, 1)$.
• All friends in the second row should move to the next cell. After this, your friend will be in the cell $(2, 2)$.

In the second test case you can remove all snow from the columns $3$ and $4$ for $22$ coins. Then you can give instructions

• All friends in the first row should move to the next cell.
• All friends in the first row should move to the next cell.
• All friends in the second row should move to the next cell.
• All friends in the second row should move to the next cell.
• All friends in the third column should move to the next cell.
• All friends in the third column should move to the next cell.
• All friends in the fourth column should move to the next cell.
• All friends in the fourth column should move to the next cell.

It can be shown that none of the friends will become ill and that it is impossible to spend less coins.

在第一个测试用例中，你可以花费 100 枚硬币清除单元格 $(2, 1)$ 和 $(2, 2)$ 上的积雪。然后你可以发出如下指令：

• 第一列中的所有朋友向左移动一格（即移至前一个单元格）。执行后，你的朋友将位于单元格 $(2, 1)$。
• 第二行中的所有朋友向右移动一格（即移至下一个单元格）。执行后，你的朋友将位于单元格 $(2, 2)$。

在第二个测试用例中，你可以花费 22 枚硬币清除第 3 列和第 4 列上的全部积雪。然后你可以发出如下指令：

• 第一行中的所有朋友向右移动一格（即移至下一个单元格）。
• 第一行中的所有朋友向右移动一格（即移至下一个单元格）。
• 第二行中的所有朋友向右移动一格（即移至下一个单元格）。
• 第二行中的所有朋友向右移动一格（即移至下一个单元格）。
• 第三列中的所有朋友向下移动一格（即移至下一个单元格）。
• 第三列中的所有朋友向下移动一格（即移至下一个单元格）。
• 第四列中的所有朋友向下移动一格（即移至下一个单元格）。
• 第四列中的所有朋友向下移动一格（即移至下一个单元格）。

可以证明：没有任何朋友会生病，且无法以更少的硬币完成该任务。