题目描述

设有 $N × M$ 的方格图，我们将其中的某些方格中填入正整数，而其他的方格中则放入数字 $0$。如下图所示:

A
 0  0  0  0  0  0  0  0
 0  0 13  0  0  6  0  0
 0  0  0  0  7  0  0  0
 0  0  0 14  0  0  0  0
 0 21  0  0  0  4  0  0
 0  0 15  0  0  0  0  0
 0 14  0  0  0  0  0  0
 0  0  0  0  0  0  0  0
                        B

某人从图的左上角的 $A$ 点出发，可以向下行走，也可以向右走，直到到达右下角的 $B$ 点。在走过的路上，他可以将格子中的正整数减 1（假设他到达方格时的数为 $x$ 且 $x>0$，则他走后的方格中的数将变为$x-1$）。如果格子中的数为 0，则不需要任何操作。

此人可以从 $A$ 点到 $B$ 点走多次。问：他最少走多少次，可以使得网格图中的所有数全变成 0。

输入格式

多组数据。

第一行：一个正整数 T，表示数据组数。

每组数据：

• 第一行：两个整数 N, M
• 接下来是一个 N × M 的非负整数矩阵 C，用来描述题目中方格图的初始状态

一个整数，表示答案。

样例输入

1
3 3
0 1 2
3 0 0
1 0 0

样例输出

5

数据范围

$30\%$ 的数据，$1 ≤ N, M ≤ 5$，$0 ≤ Cij ≤ 5$。

$50\%$ 的数据，$1 ≤ N, M ≤ 100$， $0 ≤ Cij ≤ 1000$ 。

$100\%$ 的数据，$1 ≤ T ≤ 5$，$1 ≤ N, M ≤ 1000$，$0 ≤ Cij ≤ 10^6$ 。