Maximum Sum Subgrid

You are given an N × N grid of integers. Your task is to find the contiguous subgrid (or submatrix) that has the maximum possible sum. A contiguous subgrid is defined by selecting some consecutive columns and consecutive rows from the grid, forming a rectangular section.

More formally, if you denote the grid as \( A \) with indices \( 0 \leq i, j < N \), you need to find indices \( r1, r2, c1, c2 \) such that \( 0 \le r1 \le r2 < N \) and \( 0 \le c1 \le c2 < N \) that maximize:

[ S = \sum_{i=r1}^{r2} \sum_{j=c1}^{c2} A_{ij} ]

If all numbers are negative, the maximum sum will be the largest (i.e. least negative) number in the grid.

The input begins with an integer indicating the number of test cases, followed by the description of each test case.

inputFormat

The input is read from standard input (stdin) and has the following format:

T
N
row1
row2
... 
rowN

Where:

• T is the number of test cases.
• For each test case, the first line contains an integer N, the size of the grid.
• Then N lines follow, each containing N space-separated integers representing a row of the grid.

outputFormat

For each test case, output a single integer which is the maximum sum of any contiguous subgrid, each printed on a new line to standard output (stdout).

## sample

1
3
1 -2 0
-3 4 2
1 -1 -2

6

</p>