L. Loop Land
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Mr. Nežmah received a puzzle for his birthday. The puzzle can be represented as a grid with $$$n$$$ rows and $$$m$$$ columns. Each cell can be one of 12 types, labeled with numbers from $$$0$$$ to $$$9$$$ and with $$$A$$$ and $$$B$$$. Some of the cells are static, some can be rotated by specific degrees, and some function as switches. A detailed explanation of all the types follows this graphic:

Graphic of all types of cells

All cell types except $$$0$$$ have a positive number of arms. The goal of the puzzle is to pair up all the arms inside the grid. The cells can be transformed according to their type.

  • Cell types $$$0$$$ and $$$9$$$ are static and cannot be changed.
  • Cell types $$$3$$$, $$$4$$$, $$$5$$$, $$$6$$$, $$$7$$$, and $$$8$$$ are switches, meaning that the single arm must be in exactly one of the two drawn positions.
  • Cell types $$$1$$$ and $$$2$$$ can be rotated by $$$0^\circ$$$, $$$90^\circ$$$, $$$180^\circ$$$, and $$$270^\circ$$$.
  • Cell types $$$A$$$ and $$$B$$$ can be rotated by $$$0^\circ$$$, $$$180^\circ$$$.

Nežmah wants to solve the puzzle, so he needs your help!

Input

The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 2 \cdot 10^4$$$), the number of test cases.

The first line of each test case contains integers $$$n$$$ and $$$m$$$ ($$$1 \leq n, m \leq 10^3)$$$.

The following $$$n$$$ lines contain strings of length $$$m$$$ describing the $$$n$$$ rows of the grid. The $$$j$$$-th character in the $$$i$$$-th string denotes the type of the cell in the $$$i$$$-th row and $$$j$$$-th column.

It is guaranteed that the sum of $$$n \cdot m$$$ over all test cases does not exceed $$$10^6$$$.

Output

For each test case, output $$$2n - 1$$$ lines. Each line should contain a string of length $$$2m - 1$$$. If the cell in the $$$i$$$-th row and $$$j$$$-th column is of non-zero type, the character in the $$$(2i - 1)$$$-th string on the $$$(2j - 1)$$$-th position should be 'o'. Each 'o' should have a possible construction of arms going out of it (according to the type of the appropriate cell). Vertical arms are denoted with '|' and horizontal ones with '-'. All other characters should be '.'.

A solution is guaranteed to exist, and if there are multiple solutions, you can output any of them.

Example
Input
3
4 4
2A70
2A58
87A2
21A5
2 2
68
35
7 6
065258
622143
B9BBB0
5B2B20
7B3A86
432A12
282A15
Output
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