F. Уменьшение высот
ограничение по времени на тест
2.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы играете в одну популярную sandbox-игру с трехмерным миром. Карта мира может быть представлена в виде матрицы размера $$$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$$$.

Перед первым перемещением вы можете выполнить несколько операций. В течение одной операции вы можете уменьшить высоту любой клетки на единицу. То есть вы выбираете какую-то клетку $$$(i, j)$$$ и присваиваете $$$a_{i, j} := a_{i, j} - 1$$$. Заметьте, что вы можете делать высоты меньшими или равными нулю. Также заметьте, что вы можете уменьшать высоту клетки $$$(1, 1)$$$.

Ваша задача — найти минимальное количество операций, которое необходимо выполнить, чтобы получить хотя бы один подходящий путь из клетки $$$(1, 1)$$$ в клетку $$$(n, m)$$$. Гарантируется, что ответ существует.

Вам необходимо ответить на $$$t$$$ независимых наборов тестовых данных.

Входные данные

Первая строка входных данных содержит одно целое число $$$t$$$ ($$$1 \le t \le 100$$$) — Количество наборов тестовых данных. Затем следуют $$$t$$$ наборов тестовых данных.

Первая строка набора тестовых данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n, m \le 100$$$) — количество строк и количество столбцов в карте мира. Следующие $$$n$$$ строк содержат по $$$m$$$ целых чисел каждая, где $$$j$$$-е число в $$$i$$$-й строке равно $$$a_{i, j}$$$ ($$$1 \le a_{i, j} \le 10^{15}$$$) — высоте клетки $$$(i, j)$$$.

Гарантируется, что сумма $$$n$$$ (также как сумма $$$m$$$) по всем наборам тестовых данных не превосходит $$$100$$$ ($$$\sum n \le 100; \sum m \le 100$$$).

Выходные данные

Для каждого набора тестовых данных выведите ответ — минимальное количество операций, которое необходимо выполнить, чтобы получить хотя бы один подходящий путь из клетки $$$(1, 1)$$$ в клетку $$$(n, m)$$$. Гарантируется, что ответ существует.

Пример
Входные данные
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