您正在玩一款著名的三维世界沙盒游戏。世界地图可以表示为大小为 $$$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$$$ 的单元格。
在第一次移动之前,您可以执行多项操作。在一次操作期间,您可以将任何单元格的高度减少一。 IE。您选择某个单元格 $$$(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$$$ 个整数,其中第 $$$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$$$)。
输出
对于每个测试用例,打印答案 — 为获得从单元格 $$$(1, 1)$$$ 到单元格 $$$(n, m)$$$ 的至少一条合适路径而必须执行的最少操作数。保证答案存在。
示例
输入 #1
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
输出 #1
9 49 111 864197531358023 0