You must write a solver for a puzzle that depicts a map. Each tile is square with edges corresponding to markings on a map. There are six different possible edge types: Road (R), City (C), Farm (F), Stream (S), Lake (L), and Boulders (B). Tiles will fit in a grid of rows and columns where adjacent edges must match. Tile edges on the outer edge of the grid are not adjacent to any other tile edge, i.e. no wrap around.

Input

The first line of input will contain the number of test cases, $T$ ($1 \leq T \leq 50$).

The first line of each test case will contain the number of rows and columns $R$, $C$ in a grid, ($1 \leq R, C \leq 50$).

The next $R \times C$ lines will each contain a puzzle tile, represented as $4$ characters indicating the North, East, South, and West sides.

The first tile read in for each puzzle is the starter tile. It is fixed, i.e. it cannot be rotated, and will be placed in the first row and first column of the grid. Subsequent tiles can be placed in any other location in the puzzle grid and can be rotated as necessary to find a proper fit.

Output

Output consists of the completed puzzle, $R \times 5$ lines each with $C \times 5$ characters. Each $5 \times 5$ square represents a tile and looks like the following:

+---+
| F |
|L R|
| B |
+---+

Each puzzle is guaranteed to have a single solution.

Test cases will be separated by a single blank line.

Sample Input

2
2 3
FRCR
CLLB
FFSB
FLRB
LRLC
FRSF
2 2
CCBC
CSRB
SLFF
LCRR

Sample Output

+---++---++---+
| F || B || R |
|R R||R F||F S|
| C || L || F |
+---++---++---+
+---++---++---+
| C || L || F |
|L L||L B||B F|
| R || C || S |
+---++---++---+

+---++---+
| C || R |
|C C||C R|
| B || L |
+---++---+
+---++---+
| B || L |
|B S||S F|
| R || F |
+---++---+