Maximum Sum Submatrix

You are given an \(N\times N\) integer matrix \(M\). Your task is to find the maximum possible sum of a contiguous submatrix of \(M\). A submatrix is defined by selecting two rows \(i\) and \(j\) (with \(i \le j\)) and two columns \(k\) and \(l\) (with \(k \le l\)), and taking all elements \(M_{p,q}\) with \(i \le p \le j\) and \(k \le q \le l\). The sum is given by:

\(S = \sum_{p=i}^{j} \sum_{q=k}^{l} M_{p,q}\)

Your goal is to compute the maximum \(S\) over all possible contiguous submatrices.

inputFormat

The input is given via standard input (stdin) and is formatted as follows:

• The first line contains an integer \(T\), the number of test cases.
• For each test case, the first line contains an integer \(N\), the dimension of the square matrix.
• Then \(N\) lines follow, each containing \(N\) integers separated by spaces representing the rows of the matrix.

It is guaranteed that \(N \ge 1\) and the matrix elements are integers.

outputFormat

For each test case, output a single integer on a new line which is the maximum sum of any contiguous submatrix of the given matrix. The answer should be printed to standard output (stdout).

1
3
1 2 3
4 5 6
7 8 9

45