Maximum Sub-Rectangle Sum

You are given a grid of integers where each integer represents a maintenance cost. Your task is to find the maximum sum of any sub-rectangle within the grid. A sub-rectangle is defined by choosing any contiguous block of rows and columns from the grid.

The algorithm of choice is a 2D extension of Kadane's algorithm, which is typically used for finding the maximum subarray sum in a one-dimensional array. In this problem, you have to extend it to two dimensions.

Mathematical formulation:

Given a matrix \(A\) of size \(n \times m\), find the maximum value of the sum \[ S = \sum_{i=p}^{q} \sum_{j=r}^{s} A_{ij} \] where \(0 \leq p \leq q < n\) and \(0 \leq r \leq s < m\).

Print the maximum sum for each test case.

inputFormat

The input begins with a single integer \(T\) representing the number of test cases. For each test case:

• The first line contains two integers \(n\) and \(m\), denoting the number of rows and columns in the grid respectively.
• It is followed by \(n\) lines, each containing \(m\) space-separated integers representing the grid.

All input is provided via standard input (stdin).

outputFormat

For each test case, output a single line containing one integer — the maximum sub-rectangle sum found in that grid. The answer for each test case should be printed on its own line to standard output (stdout).

## sample

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

45
-1
6
5

</p>