Mr. Nežmah 收到了一个生日谜题。这个谜题可以表示为一个 $n$ 行 $m$ 列的网格。每个网格单元可以是 12 种类型之一，分别用数字 0 到 9 以及字母 A 和 B 标记。有些单元是静态的，有些可以旋转特定的角度，还有一些作为开关使用。在以下图示之后有对所有类型的详细解释：

所有单元格类型的图示

除 0 型以外的所有单元格类型都具有正数个分支（arms）。谜题的目标是将网格内的所有分支两两配对。单元格可以根据其类型进行变换。

• 0 型和 9 型单元格是静态的，无法改变。
• 3、4、5、6、7 和 8 型单元格是开关，这意味着其单个分支必须处于画出的两个位置之一。
• 1 型和 2 型单元格可以旋转 $0^\circ$、$90^\circ$、$180^\circ$ 和 $270^\circ$。
• A 型和 B 型单元格可以旋转 $0^\circ$ 和 $180^\circ$。

Nežmah 想要解开这个谜题，所以他需要你的帮助！

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 2 \cdot 10^4$)，表示测试用例的数量。

每个测试用例的第一行包含两个整数 $n$ 和 $m$ ($1 \le n, m \le 10^3$)。

接下来的 $n$ 行，每行包含一个长度为 $m$ 的字符串，描述网格的 $n$ 行。第 $i$ 个字符串中的第 $j$ 个字符表示第 $i$ 行第 $j$ 列的单元格类型。

保证所有测试用例中 $n \cdot m$ 的总和不超过 $10^6$。

输出格式

对于每个测试用例，输出 $2n - 1$ 行。每行应包含一个长度为 $2m - 1$ 的字符串。如果第 $i$ 行第 $j$ 列的单元格是非零类型，则第 $2i - 1$ 个字符串中第 $2j - 1$ 个位置的字符应为 'o'。每个 'o' 应该有从其延伸出的分支的可能结构（根据相应单元格的类型）。垂直分支用 '|' 表示，水平分支用 '-' 表示。所有其他字符应为 '.'。

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

样例

输入样例 1

3
4 4
2A70
2A58
87A2
21A5
2 2
68
35
7 6
065258
622143
B9BBB0
5B2B20
7B3A86
432A12
282A15

输出样例 1

o-o-o..
|.|....
o-o-o.o
......|
o.o-o-o
|...|..
o-o-o-o
o.o
|.|
o.o
..o-o.o-o.o
......|...|
o.o-o.o.o.o
|.|.|.|.|..
o-o-o.o-o..
|.|.|.|.|..
o.o-o.o-o..
..|...|....
o-o.o-o-o.o
..|.......|
o.o.o-o-o-o
|...|.|....
o-o.o-o-o-o