Maximum Subgrid Sum

You are given a two-dimensional grid of integers. Your task is to find the subgrid (i.e. a contiguous rectangle of cells) that has the maximum sum among all possible subgrids of the grid.

Formally, if the grid is treated as a matrix \(A\) of size \(N \times M\), then a subgrid is defined by four indices \(i, j, k, l\) with \(1 \le i \le k \le N\) and \(1 \le j \le l \le M\). The sum of this subgrid is defined as:

\[ S = \sum_{p=i}^{k} \sum_{q=j}^{l} A_{p,q} \]

Your goal is to choose \(i, j, k,\) and \(l\) such that \(S\) is maximized. A well‐known approach to solving such problems in \(O(M^2 \cdot N)\) time is to fix the left and right boundaries of the subgrid and then apply Kadane's algorithm on the sums of rows for the defined column boundaries.

inputFormat

The first line of the input contains an integer \(T\) denoting the number of test cases. The description of each test case is as follows:

1. The first line of each test case contains two integers \(N\) and \(M\) indicating the number of rows and columns of the grid, respectively.
2. The following \(N\) lines each contain \(M\) space-separated integers, representing the rows of the grid.

Input is read from standard input (stdin).

outputFormat

For each test case, output a single integer representing the maximum sum of any subgrid in the given grid. Each answer should be printed on a new line to standard output (stdout).

## sample

3
2 2
1 2
-1 -3
3 3
1 -2 3
4 5 -6
-7 8 9
1 5
-1 -1 -1 -1 -1

3
17
-1

</p>