Maximum Boundary Sum Submatrix

You are given a square matrix of integers. Your task is to find a submatrix (defined by its top‐left and bottom‐right coordinates) such that the sum of the boundary elements is maximized.

For any submatrix defined by top‐left coordinate \((i_1, j_1)\) and bottom‐right coordinate \((i_2, j_2)\), the boundary sum is defined as the sum of all elements on the perimeter of the submatrix. In other words, if you denote the matrix by \(A\), the boundary sum is computed as:

[ S = \sum_{j=j_1}^{j_2} A[i_1][j] + \sum_{j=j_1}^{j_2} A[i_2][j] + \sum_{i=i_1+1}^{i_2-1} A[i][j_1] + \sum_{i=i_1+1}^{i_2-1} A[i][j_2] ]

Note that if the submatrix consists of only one row or one column, you should take care not to double count elements.

You need to process multiple test cases. For each test case, output the coordinates of the submatrix with the maximum boundary sum and the maximum sum itself. The coordinates should be output in the following order: i1 j1 i2 j2 sum.

inputFormat

The first line contains an integer \(T\) representing the number of test cases.

For each test case, the first line contains an integer \(n\) (the size of the square matrix). The next \(n\) lines each contain \(n\) space-separated integers, representing the rows of the matrix.

Input Example:

2
3
1 2 3
4 5 6
7 8 9
2
10 20
30 40

outputFormat

For each test case, output a single line containing five integers: i1 j1 i2 j2 sum, where \((i1, j1)\) is the top‐left and \((i2, j2)\) is the bottom‐right coordinate of the submatrix with the maximum boundary sum, and sum is that maximum boundary sum.

Output Example:

0 0 2 2 40
0 0 1 1 100

## sample

1
3
1 2 3
4 5 6
7 8 9

0 0 2 2 40