Вы играете в одну популярную 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\) независимых наборов тестовых данных.
Выходные данные
Для каждого набора тестовых данных выведите ответ — минимальное количество операций, которое необходимо выполнить, чтобы получить хотя бы один подходящий путь из клетки \((1, 1)\) в клетку \((n, m)\). Гарантируется, что ответ существует.