给定一个大小为 $n \times n$ 的棋盘，其中 $n$ 为奇数。对于棋盘上的每个格子，给出了在该处建造雷达的代价。雷达覆盖一个边长为 $n$ 的正方形区域（边与棋盘边平行），且其中心位于雷达所在的格子。你的任务是最小化建造若干雷达的总代价，使得棋盘上的每个格子至少被覆盖一次。此外，你需要解决多个测试用例。

输入格式

第一行包含一个整数 $t$ ($t \ge 1$)，表示测试用例的数量。 接下来是 $t$ 个测试用例的描述。 每个测试用例的第一行包含一个整数 $n$ ($1 \le n \le 499; n$ 为奇数)，表示棋盘的维度。 接下来的 $n$ 行给出了棋盘的描述。 第 $i$ 行包含 $n$ 个整数 $a_{i,1}, a_{i,2}, \dots, a_{i,n}$ ($1 \le a_{i,j} \le 10^9$)，其中 $a_{i,j}$ 表示在第 $i$ 行第 $j$ 列的格子中建造雷达的代价。 保证单个文件中所有 $n^2$ 的总和不超过 $500\,000$。

输出格式

输出应包含 $t$ 行。第 $i$ 行应包含一个整数，表示第 $i$ 个测试用例中建造雷达的最小代价。

样例

输入 1

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

1
5

说明

在第一个样例中，只建造一个雷达是值得的。在第二个样例中，建造三个雷达是值得的。雷达的最佳位置以及它们覆盖的区域如下图所示：