To The Max

给定一个整数型的二维数组，从这个二维数组中找出一个子矩形，子矩形的大小为1×1或更大。一个子矩形的总和指在这个矩形中的所有元素的总和。总和最大的子矩形被称为最大子矩形。

如下示例：

0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
该矩阵的最大子矩阵的为左下角的一个子矩阵：

9 2
-4 1
-1 8
该矩阵的总和为15。

测试数据有多组。输入整数T，表示有T组测试数据。每组测试数据，输入n，代表n*n的矩形。接下来n行每行输入n个整数。n<=100。

每组测试数据输出一行答案，为最大子矩阵的总和。

1
4
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2

15