B. 矩阵稳定化

时间限制：2 秒
内存限制：256 兆字节

给定一个 $n \times m$ 的矩阵，行从上到下编号为 $1$ 到 $n$，列从左到右编号为 $1$ 到 $m$。第 $i$ 行第 $j$ 列的元素记为 $a_{ij}$。

考虑以下稳定化矩阵 $a$ 的算法：

1. 找到一个单元格 $(i,j)$，使得它的值严格大于它所有邻居单元格的值。如果没有这样的单元格，则算法终止。如果有多个这样的单元格，则选择 $i$ 最小的那个；如果仍有多个，则选择 $j$ 最小的那个。
2. 设置 $a_{ij} = a_{ij} - 1$。
3. 转到步骤 1。

在本题中，单元格 $(a,b)$ 和 $(c,d)$ 被认为是邻居当且仅当它们共享一条公共边，即 $|a-c| + |b-d| = 1$。

你的任务是输出算法执行结束后的矩阵 $a$。可以证明该算法不会无限运行。

输入

每个测试包含多组输入数据。第一行包含一个整数 $t$（$1 \le t \le 10^4$）——输入数据的组数。接下来是各组数据的描述。

每组输入数据的第一行包含两个整数 $n$ 和 $m$（$1 \le n, m \le 100$，$n \cdot m > 1$）——矩阵 $a$ 的行数和列数。

接下来的 $n$ 行描述矩阵的对应行。第 $i$ 行包含 $m$ 个整数 $a_{i1}, a_{i2}, \dots, a_{im}$（$1 \le a_{ij} \le 10^9$）。

保证所有输入数据的 $n \cdot m$ 之和不超过 $2 \cdot 10^5$。

输出

对于每组输入数据，输出 $n$ 行，每行 $m$ 个数，表示算法执行结束后的矩阵 $a$。

示例

输入

6
1 2
3 1
2 1
1
1
2 2
1 2
3 4
2 3
7 4 5
1 8 10
5 4
92 74 31 74
74 92 17 7
31 17 92 3
74 7 3 92
7 31 1 1
3 3
1000000000 1 1000000000
1 1000000000 1
1000000000 1 1000000000

输出

1 1 
1 
1 
1 2 
3 3 
4 4 5 
1 8 8 
74 74 31 31 
74 74 17 7 
31 17 17 3 
31 7 3 3 
7 7 1 1 
1 1 1 
1 1 1 
1 1 1 

注释

在第一组输入数据中，算法会连续两次选择单元格 $(1,1)$，然后终止。

在第二组输入数据中，没有单元格的值严格大于所有邻居的值。

在第三组输入数据中，算法会选择单元格 $(2,2)$，然后终止。

在第四组输入数据中，算法会选择单元格 $(1,1)$ 三次，然后选择单元格 $(2,3)$ 两次。