CF1353F.Decreasing Heights

You are playing one famous sandbox game with the three-dimensional world. The map of the world can be represented as a matrix of size $n \times m$, where the height of the cell $(i, j)$ is $a_{i, j}$.

You are in the cell $(1, 1)$ right now and want to get in the cell $(n, m)$. You can move only down (from the cell $(i, j)$ to the cell $(i + 1, j)$) or right (from the cell $(i, j)$ to the cell $(i, j + 1)$). There is an additional restriction: if the height of the current cell is $x$ then you can move only to the cell with height $x+1$.

Before the first move you can perform several operations. During one operation, you can decrease the height of any cell by one. I.e. you choose some cell $(i, j)$ and assign (set) $a_{i, j} := a_{i, j} - 1$. Note that you can make heights less than or equal to zero. Also note that you can decrease the height of the cell $(1, 1)$.

Your task is to find the minimum number of operations you have to perform to obtain at least one suitable path from the cell $(1, 1)$ to the cell $(n, m)$. It is guaranteed that the answer exists.

You have to answer $t$ independent test cases.

你正在玩一款著名的沙盒游戏，其世界是三维的。游戏地图可以表示为一个 $n \times m$ 的矩阵，其中单元格 $(i, j)$ 的高度为 $a_{i, j}$。

你当前位于单元格 $(1, 1)$，目标是到达单元格 $(n, m)$。你每次只能向下移动（从单元格 $(i, j)$ 移动到 $(i + 1, j)$）或向右移动（从单元格 $(i, j)$ 移动到 $(i, j + 1)$）。此外还有一个限制条件：若当前单元格的高度为 $x$，则你只能移动到高度恰好为 $x+1$ 的单元格。

在第一次移动之前，你可以执行若干次操作。每次操作中，你可以将任意一个单元格的高度减小 $1$。即：你选择某个单元格 $(i, j)$，并令 $a_{i, j} := a_{i, j} - 1$。注意，单元格高度可被减至 $0$ 或负数；同时，你也可以降低起点单元格 $(1, 1)$ 的高度。

你的任务是求出为使得至少存在一条从 $(1, 1)$ 到 $(n, m)$ 的合法路径所需执行的最少操作次数。题目保证答案一定存在。

你需要回答 $t$ 个相互独立的测试用例。

The first line of the input contains one integer $t$ ($1 \le t \le 100$) — the number of test cases. Then $t$ test cases follow.

The first line of the test case contains two integers $n$ and $m$ ($1 \le n, m \le 100$) — the number of rows and the number of columns in the map of the world. The next $n$ lines contain $m$ integers each, where the $j$-th integer in the $i$-th line is $a_{i, j}$ ($1 \le a_{i, j} \le 10^{15}$) — the height of the cell $(i, j)$.

It is guaranteed that the sum of $n$ (as well as the sum of $m$) over all test cases does not exceed $100$ ($\sum n \le 100; \sum m \le 100$).

输入的第一行包含一个整数 $t$（$1 \le t \le 100$），表示测试用例的数量。随后是 $t$ 个测试用例。

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \le n, m \le 100$），分别表示世界地图的行数和列数。接下来的 $n$ 行每行包含 $m$ 个整数，其中第 $i$ 行的第 $j$ 个整数为 $a_{i, j}$（$1 \le a_{i, j} \le 10^{15}$），表示单元格 $(i, j)$ 的高度。

保证所有测试用例中 $n$ 的总和（以及 $m$ 的总和）均不超过 $100$（即 $\sum n \le 100$；$\sum m \le 100$）。

For each test case, print the answer — the minimum number of operations you have to perform to obtain at least one suitable path from the cell $(1, 1)$ to the cell $(n, m)$. It is guaranteed that the answer exists.

对于每个测试用例，输出答案——即从单元格 $(1, 1)$ 到单元格 $(n, m)$ 获得至少一条合适路径所需执行的最少操作次数。保证答案存在。