桜子与水

题目描述

在与浩介的旅行中，桜子和浩介发现了一个可以用 $n \times n$ 的矩阵表示的山谷，其中第 $i$ 行与第 $j$ 列的交点是高度为 $a_{i,j}$ 的山。

如果 $a_{i,j} < 0$ 那么那里有一个湖。

浩介非常害怕水，因此桜子需要帮助他： 利用她的魔法，她可以选择一个方形山脉区域，并将该区域主对角线上的每个山的高度增加一个单位。

更正式地说，她可以选择一个子矩阵，左上角位于 $(i,j)$，右下角位于 $(p,q)$，并且有 $p-i=q-j$ 的关系。然后她可以对所有 $0 \le k \le p-i$ 的 $k$，将位于 $(i+k)$ 行与 $(j+k)$ 列交点的每个元素增加 $1$。

确定桜子必须使用她的魔法的最少次数，以使没有湖泊存在。

输入格式

第一行是一个整数 $t(1 \le t \le 200)$ — 测试用例的数量。

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

每个测试用例的第一行包含一个数字 $n(1 \le n \le500)$。

接下来的 $n$ 行包含 $n$ 个以空格分隔的整数，这些整数对应于山谷中山的高度 $a_{i}(-10^{5} \le a_{i} \le 10^{5})$。

保证所有测试用例中 $\sum n \le 1000$。

输出格式

对于每个测试用例，输出桜子必须使用她的魔法的最少次数，以使所有湖泊消失。