Minimum Defense Strength

You are given K regions, each represented by a 2D grid of integers. Each cell in the grid indicates the strength at that position. A line of defense may be a full row, a full column, or one of the two diagonals (the primary diagonal or the secondary diagonal). The primary diagonal sums the elements from the top‐left to the bottom‐right, while the secondary diagonal sums the elements from the top‐right to the bottom‐left.

The formulas for the diagonals are given by:

• Primary diagonal: \(\sum_{i=0}^{\min(P,Q)-1} grid[i][i]\)
• Secondary diagonal: \(\sum_{i=0}^{\min(P,Q)-1} grid[i][Q-i-1]\)

Your task is to compute the sum of each possible line of defense in a region and then determine the minimum among these sums. Do this for each region and output the result on a separate line.

inputFormat

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

K
P1 Q1
row1
row2
... (P1 rows each with Q1 integers)
P2 Q2
row1
row2
... (P2 rows each with Q2 integers)
...

Here, K is the number of regions. For each region, the first line contains two integers P (number of rows) and Q (number of columns), followed by P lines each containing Q space-separated integers representing the grid.

outputFormat

For each region, output a single line to standard output (stdout) containing one integer: the minimum sum among all rows, columns, and the two diagonals.

## sample

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

15
3

</p>