Problem F
Safe Lake

There is a square lake that is exactly $n$ by $n$ meters. Each square meter of the lake has its own current, which directs items either up, down, left, or right. We say the lake is safe if, no matter what position you start in, you will eventually reach the shore (leave the borders of the lake) by following the current.

You know the current for some locations in the lake. Is it possible that the lake is safe? If so, recover one set of possible currents for the unknown locations.

The below image shows the first sample input, as well as one assignment of currents to unknown locations that makes the lake safe.

If there are multiple solutions, print any.

Input

The first line of the input contains a single integer $t$ ($1 \le t \le 625$) —the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($2\le n \le 500$) —the size of the lake.

The next $n$ lines of the input for each tests case contain $n$ characters each. Each of these characters is one of $U$, $D$, $L$, $R$, or $?$, indicating that the current at that location is upwards, downwards, leftwards, rightwards, or unknown, respectively.

It is guaranteed that the sum of $n$ over all test cases is at most $2000$.

Output

For each test case, if there is no solution, print $-1$.

Otherwise, print $n$ lines of $n$ characters each, in the same format as the input, representing a safe assignment of currents. The output should not have any $?$ characters, and for any location in the input where the current is known, the output should have the same current in that location.

5
5
LU?DU
RUD?L
?R?DL
?DU??
DL?UL
3
RD?
U?D
?UL
4
????
????
????
????
2
??
RL
3
UDR
DLR
DUU

LUUDU
RUDLL
URRDL
RDURR
DLDUL
-1
RRRR
URRD
UULD
ULLL
-1
UDR
DLR
DUU