题目描述

大雪过后，小 w 需要打扫一下自己的院子，使得凹凸不平的雪堆看起来至少更整齐一些。小 w 的院子可以视作一个 $n \times m$ 的网格，第 $i$ 行第 $j$ 列的格子内覆盖了相对高度为 $h_{i,j}$ 的积雪。小 w 有以下几种清理雪堆的操作：

• 选择 $1 \le i < n, 1 \le j \le m$，将第 $i$ 行第 $j$ 列的雪堆推到下一行上，此操作会使得 $h_{i,j}$ 减 $1$，$h_{i+1,j}$ 加 $1$。此操作不需要代价。
• 选择 $1 \le i \le n, 1 \le j < m$，将第 $i$ 行第 $j$ 列的雪堆推到下一列上。此操作会使得 $h_{i,j}$ 减 $1$，$h_{i,j+1}$ 加 $1$。此操作不需要代价。
• 选择 $1 \le i \le n, 1 \le j \le m$，给第 $i$ 行第 $j$ 列的雪堆造雪。此操作会使得 $h_{i,j}$ 加 $1$。此操作需要 $1$ 的代价。
• 选择 $1 \le i \le n, 1 \le j \le m$，给第 $i$ 行第 $j$ 列的雪堆抽雪。此操作会使得 $h_{i,j}$ 减 $1$。此操作需要 $1$ 的代价。

小 w 想要进行若干次操作使得所有 $h_{i,j}$ 都为 $0$，且需要的代价最小。你能帮他计算一下最小的代价吗？

输入格式

输入第一行包含一个整数 $T$ ($1 \le T \le 10^6$)，表示测试数据组数。

接下来依次输入每组测试数据，对于每组测试数据：

输入第一行包含两个整数 $n,m$ ($1 \le n,m \le 10^3$)，表示院子的行数与列数。

接下来 $n$ 行第 $i$ 行包含 $m$ 个整数 $h_{i,1},h_{i,2},\ldots, h_{i,m}$ ($-10^9 \le h_{i,j} \le 10^9$)，第 $j$ 个整数表示第 $i$ 行第 $j$ 列格子上积雪的相对高度。

对于所有数据，保证它们的 $n \cdot m$ 之和不超过 $10^6$。

输出格式

对于每组测试数据，输出一行一个整数，表示小 w 完成目标需要的最小代价。

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

5
0
3