After a heavy snowfall, Little W needs to clear his yard to make the uneven snow piles look neater. Little W's yard can be viewed as an $n \times m$ grid, where the cell at the $i$-th row and $j$-th column is covered with snow of relative height $h_{i,j}$. Little W has the following operations to clear the snow:

1. Choose $1 \le i < n, 1 \le j \le m$, and push the snow at the $i$-th row and $j$-th column to the next row. This operation decreases $h_{i,j}$ by 1 and increases $h_{i+1,j}$ by 1. This operation costs 0.
2. Choose $1 \le i \le n, 1 \le j < m$, and push the snow at the $i$-th row and $j$-th column to the next column. This operation decreases $h_{i,j}$ by 1 and increases $h_{i,j+1}$ by 1. This operation costs 0.
3. Choose $1 \le i \le n, 1 \le j \le m$, and add snow to the $i$-th row and $j$-th column. This operation increases $h_{i,j}$ by 1. This operation costs 1.
4. Choose $1 \le i \le n, 1 \le j \le m$, and remove snow from the $i$-th row and $j$-th column. This operation decreases $h_{i,j}$ by 1. This operation costs 1.

Little W wants to perform a sequence of operations such that all $h_{i,j}$ become 0, with the minimum total cost. Can you help him calculate the minimum cost?

Input

There are multiple test cases. The first line contains an integer $T$ ($1 \le T \le 10^6$), representing the number of test cases. For each test case:

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 each contain $m$ integers $h_{i,1}, h_{i,2}, \dots, h_{i,m}$ ($-10^9 \le h_{i,j} \le 10^9$), where the $j$-th integer represents the relative height of the snow at the $i$-th row and $j$-th column.

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

Output

For each test case, output a single integer representing the minimum cost required for Little W to achieve his goal.

Examples

Input 1

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

Output 1

5
0
3