题目描述

在与浩介的旅途中，樱子和浩介发现了一个山谷，这个山谷可以表示为一个大小为 $n \times n$ 的矩阵，在 $i$ 行和 $j$ 列的交点上有一座高度为 $a_{i,j}$ 的山；如果 $a_{i,j} < 0$，那么那里有一个湖。

浩介非常怕水，所以樱子需要帮助他：

• 她可以用魔法选择一个正方形的山峰区域，并将该区域主对角线上的每座山峰的高度正好增加一个。

更正式地说，她可以选择一个左上角位于 $(i, j)$，右下角位于 $(p, q)$ 的子矩阵，满足 $p-i=q-j$。然后在 $(i + k)$ 行和 $(j + k)$ 列的交点处的每个元素上加 $1$，其中 $k$ 满足 $0 \le k \le p-i$。

求樱子使用魔法的最少次数，这样就没有湖泊了。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 200$），测试用例数。

每个测试用例的描述如下：

• 每个测试用例的第一行包含一个数字 $n$（$1 \le n \le 500$）。
• 接下来的每行 $n$ 都由 $n$ 个整数组成，中间用空格隔开，这些整数对应山谷中的山高 $a$（$-10^5 \le a_{i,j} \le 10^5$）。

保证所有测试用例中 $n$ 的总和不超过 $1000$。

输出格式

针对每个测试案例，输出樱子使用魔法使所有湖泊消失的最少次数。

说明/提示

样例解释

样例 1

矩阵中没有负数（即没有湖），因此不需要任何魔法操作。

样例 2

• 只有一个湖位于 $(1,1)$，高度为 $-1$。
• 我们需要选择一个包含 $(1,1)$ 的正方形区域，并对其主对角线上的元素加 $1$。
• 因此答案是 $1$。

样例 3

• 湖位于 $(2,1)$、$(2,3)$ 和 $(3,3)$，高度分别为 $-2$、$-1$ 和 $-1$。
• 一种可能的操作步骤：
  1. 选择 $2 \times 2$ 的正方形（从 $(2,1)$ 到 $(3,2)$），主对角线为 $(2,1)$ 和 $(3,2)$：
     • $(2,1)$ 变为 $-2 + 1 = -1$。
     • $(3,2)$ 变为 $0 + 1 = 1$。
     • 矩阵变为：

       [ 1,  2,  3]
       [-1,  1, -1]
       [ 0,  1, -1]
       

  2. 选择 $1 \times 1$ 的正方形（仅 $(2,1)$），操作 $1$ 次：
     • $(2,1)$ 变为 $-1 + 1 = 0$。
  3. 选择 $1 \times 1$ 的正方形（仅 $(2,3)$），操作 $1$ 次：
     • $(2,3)$ 变为 $-1 + 1 = 0$。
  4. 选择 $1 \times 1$ 的正方形（仅 $(3,3)$），操作 $1$ 次：
     • $(3,3)$ 变为 $-1 + 1 = 0$。
• 最终矩阵：

[1, 2, 3]
[0, 1, 0]
[0, 1, 0]

• 总操作次数：$4$。

样例解释由 DeepSeek V3 完成。

样例

4
1
1
2
-1 2
3 0
3
1 2 3
-2 1 -1
0 0 -1
5
1 1 -1 -1 3
-3 1 4 4 -4
-1 -1 3 0 -5
4 5 3 -3 -1
3 1 -3 -1 5

0
1
4
19