题目描述

给你一个n×n的整数矩阵，在上面找一个子矩阵，使子矩阵中所有元素的和最大。

输入格式

输入数据的第一行为一个正整数T，表示有T组测试数据。每一组测试数据的第一行为一个正整数n（0

输出格式

对于每组数据，输出一个整数，表示子矩阵的最大和。

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

15