B. 樱子与水

• 每次测试的时间限制：2 秒
• 每次测试的内存限制：256 兆字节

樱子和康介在旅途中发现了一个山谷，山谷可以用一个 $n \times n$ 的矩阵来表示。在第 $i$ 行第 $j$ 列的交汇处，有一座高度为 $a_{i,j}$ 的山。如果 $a_{i,j} < 0$，那么那里就有一个湖。

康介非常怕水，因此樱子需要帮助他：

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

更正式地说，她可以选择一个子矩阵，其左上角位于 $(i,j)$，右下角位于 $(p,q)$，满足 $p - i = q - j$。然后，对于所有的 $k$（$0 \le k \le p - i$），她将位于第 $(i+k)$ 行、第 $(j+k)$ 列的元素各增加 $1$。

请计算樱子至少需要使用多少次魔法，才能使得山谷中不再有湖（即所有 $a_{i,j} \ge 0$）。

输入

第一行包含一个整数 $t$（$1 \le t \le 200$），表示测试用例的数量。
每个测试用例的描述如下：

• 第一行是一个整数 $n$（$1 \le n \le 500$）。
• 接下来的 $n$ 行，每行包含 $n$ 个整数，表示山谷中各个位置的山的高度 $a_{i,j}$（$-10^5 \le a_{i,j} \le 10^5$）。

数据保证所有测试用例的 $n$ 之和不超过 $1000$。

输出

对于每个测试用例，输出最少需要使用魔法的次数，使得所有湖消失。

示例

输入

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