Connect the Cells

Connect the Cells is a well known puzzle game, and a version of it exists on most mobile devices.

The board has $N$ rows with $N$ cells in each row. Every cell is either empty or colored. An empty cell is written as 0, and a colored cell is written as a digit from 1 to 9. Every color that appears on the board appears in exactly two cells. Your task is to connect the two cells of each color while leaving no empty cell behind.

Two cells are adjacent when they share an edge, vertically or horizontally. In every input board, two cells of the same color are never adjacent.

Here is how two cells of the same color are connected. Each color has its own pen, and a cell takes that color as soon as the pen touches it. Put the pen on one of the two cells of the color, keep moving it to an adjacent cell through empty cells, and finally move it onto the second cell of the same color. The moment the pen enters that second cell the two cells count as connected, so you stop using that pen and start connecting another color if any color is left. The pen cannot leave the board and cannot color the same cell twice.

The pen may stand on an already colored cell only when the cell is the start cell or the end cell of its own color, and it may stand on each of those two cells only once.

The first line has the number of test cases $T$ ($1 \le T \le 100$). The $T$ test cases follow. The first line of a test case has the board size $N$ ($3 \le N \le 8$). The next $N$ lines each hold $N$ digits, and one digit describes one cell. A 0 means an empty cell.

If the board holds $X$ distinct colors, those colors are named with the digits from 1 to $X$ ($1 \le X \le 9$). Every test case has at least one solution, and every input board satisfies all of the conditions above.

For each test case first print Case n: on its own line, where $n$ is the test case number starting from 1. Then print $N$ lines of $N$ characters each. The $j$-th character of the $i$-th line is the direction the pen used to leave the cell in row $i$ and column $j$: U for up, R for right, D for down, L for left, and X if that cell is the last cell the pen entered after connecting the cells of its color.

Several solutions can exist. Print the lexicographically smallest one. Read the $N$ lines you print from top to bottom as one string of $N^2$ characters, and compare characters so that they grow in the order D, L, R, U, X.