Decreasing Heights
Description
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.
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$).
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.
Input
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$).
Output
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.
Samples
5
3 4
1 2 3 4
5 6 7 8
9 10 11 12
5 5
2 5 4 8 3
9 10 11 5 1
12 8 4 2 5
2 2 5 4 1
6 8 2 4 2
2 2
100 10
10 1
1 2
123456789876543 987654321234567
1 1
42
9
49
111
864197531358023
0