给你一个大小为 $N \times M$ 的网格。你的任务是用 1、2、3 或 4 这四种颜色之一为网格的每个单元格着色。

规则只有一个：任何两个相邻的单元格必须具有不同的颜色。如果两个单元格共享一条公共边，则认为它们是相邻的。

网格中的某些单元格可能已经着色。这些预先着色的单元格仅位于网格的边界上。你必须为所有剩余的空白单元格着色，以创建一个满足规则的完整网格。

输入格式

输入的第一行包含一个整数 $T$，表示测试用例的数量。

每个测试用例的第一行包含两个整数 $N$ 和 $M$。

接下来的 $N$ 行描述网格的初始状态。每行包含 $M$ 个空格分隔的整数。值为 0 表示空白单元格，而 1 到 4 的值表示已涂有该特定颜色的单元格。

输出格式

对于每个测试用例，输出 $N$ 行，表示完成后的网格。

每行应包含 $M$ 个空格分隔的整数，其中每个整数是 1 到 4 之间的一种颜色。

如果存在多个解，你可以输出其中任意一个。

数据范围

• $1 \le T \le 8000$
• $5 \le N, M \le 2 \cdot 10^5$
• 所有测试用例的 $N \times M$ 之和不超过 $2 \cdot 10^5$。
• 在初始网格中，任何非零单元格仅位于边界上（第一行、最后一行、第一列或最后一列）。
• 保证对于给定的输入，总是存在解。

样例

输入 1

2
5 5
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
7 7
1 0 0 2 0 0 3
0 0 0 0 0 0 0
0 0 0 0 0 0 0
4 0 0 0 0 0 4
0 0 0 0 0 0 0
0 0 0 0 0 0 0
3 0 0 2 0 0 1

输出 1

1 2 1 2 1
2 1 2 1 2
1 2 1 2 1
2 1 2 1 2
1 2 1 2 1
1 2 1 2 1 2 3
2 1 2 1 2 3 1
1 2 1 2 1 4 2
4 1 2 1 2 1 4
1 2 1 2 1 2 1
2 3 2 1 2 1 2
3 1 3 2 1 2 1