Problem Description

After a heavy snow, little w needs to clean up his yard so that the uneven snow piles look at least a bit neater. The yard can be seen as an $n \times m$ grid. The cell in row $i$ and column $j$ is covered by snow with relative height $h_{i,j}$. Little w has the following operations to deal with the snow piles:

• Choose $1 \le i < n, 1 \le j \le m$, and push the snow pile at row $i$, column $j$ to the next row. This operation decreases $h_{i,j}$ by $1$ and increases $h_{i+1,j}$ by $1$. This operation has no cost.
• Choose $1 \le i \le n, 1 \le j < m$, and push the snow pile at row $i$, column $j$ to the next column. This operation decreases $h_{i,j}$ by $1$ and increases $h_{i,j+1}$ by $1$. This operation has no cost.
• Choose $1 \le i \le n, 1 \le j \le m$, and make snow on the pile at row $i$, column $j$. This operation increases $h_{i,j}$ by $1$. This operation costs $1$.
• Choose $1 \le i \le n, 1 \le j \le m$, and remove snow from the pile at row $i$, column $j$. This operation decreases $h_{i,j}$ by $1$. This operation costs $1$.

Little w wants to perform some operations to make all $h_{i,j}$ equal to $0$, with the minimum total cost. Can you help him compute the minimum cost?

Input Format

The first line contains an integer $T$ ($1 \le T \le 10^6$), indicating the number of test cases.

Then each test case is given as follows:

The first line contains two integers $n, m$ ($1 \le n, m \le 10^3$), representing the number of rows and columns of the yard.

The next $n$ lines describe the grid. Line $i$ contains $m$ integers $h_{i,1}, h_{i,2}, \ldots, h_{i,m}$ ($-10^9 \le h_{i,j} \le 10^9$), where the $j$-th integer is the relative snow height in the cell at row $i$, column $j$.

For all testdata, it is guaranteed that the sum of $n \cdot m$ over all test cases does not exceed $10^6$.

Output Format

For each test case, output one integer per line, representing the minimum cost for little w to reach the goal.

3
1 1
5
1 2
1 -1
2 2
-1 0
1 1

5
0
3

Hint

Translated by ChatGPT 5