在与 Kosuke 的旅程中,Sakurako 和 Kosuke 发现了一个山谷,可以表示为大小为 $$$n \times n$$$ 的矩阵,其中第 $$$i$$$ 行和第 $$$j$$$ 列的交叉点是一座高度为 $$$a_{i,j}$$$ 的山。如果 $$$a_{i,j} < 0$$$,则那里有一个湖。
小介非常怕水,所以樱子需要帮助他:
- 凭借她的魔法,她可以选择一个正方形的山脉区域,并将该区域主对角线上的每座山脉的高度增加一倍。
更正式地说,她可以选择一个左上角位于 $$$(i, j)$$$ 且右下角位于 $$$(p, q)$$$ 的子矩阵,这样 $$$p-i=q-j$$$。然后,对于所有 $$$k$$$,她可以向第 $$$(i + k)$$$ 行和第 $$$(j + 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
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
输出 #1
0 1 4 19