칸 잇기

칸 잇기는 널리 알려진 퍼즐 게임이고, 휴대전화용 버전도 쉽게 찾을 수 있다.

게임판은 $N$개의 행으로 이루어지고 각 행에는 $N$개의 칸이 있다. 각 칸은 비어 있거나 색이 칠해져 있다. 빈 칸은 0으로 적고, 색칠된 칸은 1부터 9까지의 숫자로 적는다. 게임판에 나타나는 색은 저마다 정확히 두 칸에 나타난다. 같은 색 두 칸을 색마다 모두 이으면서 빈 칸을 하나도 남기지 않는 것이 목표다.

두 칸이 가로나 세로로 변을 맞대고 있으면 두 칸은 인접하다. 입력으로 주어지는 게임판에서 같은 색으로 칠해진 두 칸은 절대 인접하지 않는다.

같은 색 두 칸은 이렇게 잇는다. 색마다 펜이 하나씩 있고, 펜이 어떤 칸에 닿으면 그 칸은 그 색으로 칠해진다. 먼저 그 색의 두 칸 중 하나에 펜을 올려놓고, 빈 칸을 지나 인접한 칸으로 계속 옮기다가 마지막에 같은 색의 나머지 칸으로 옮긴다. 펜이 그 색의 두 번째 칸에 들어가는 순간 두 칸은 이어진 것으로 보고, 그 펜은 더 쓰지 않는다. 아직 남은 색이 있으면 다음 색을 잇는다. 펜은 게임판 밖으로 나갈 수 없고, 같은 칸을 두 번 칠할 수도 없다.

펜이 이미 색칠된 칸에 있을 수 있는 경우는 자기 색의 시작 칸이나 도착 칸일 때뿐이고, 그 두 칸에도 각각 한 번씩만 있을 수 있다.

첫째 줄에 테스트 케이스의 수 $T$가 주어진다 ($1 \le T \le 100$). 이어서 $T$개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫째 줄에는 게임판의 크기 $N$이 주어진다 ($3 \le N \le 8$). 다음 $N$개의 줄에는 각각 숫자 $N$개가 주어지고, 숫자 하나가 칸 하나를 나타낸다. 0은 빈 칸을 뜻한다.

게임판에 색이 $X$가지 있으면 그 색의 이름은 1부터 $X$까지의 숫자다 ($1 \le X \le 9$). 모든 테스트 케이스에는 해가 적어도 하나 있고, 입력 게임판은 위 조건을 모두 만족한다.

각 테스트 케이스마다 먼저 Case n:을 한 줄에 출력한다. $n$은 1부터 시작하는 테스트 케이스 번호다. 이어서 $N$개의 줄을 출력하고, 각 줄은 문자 $N$개로 이루어진다. $i$번째 줄의 $j$번째 문자는 $i$행 $j$열 칸에서 펜이 빠져나간 방향을 나타낸다. 위쪽은 U, 오른쪽은 R, 아래쪽은 D, 왼쪽은 L로 적고, 그 칸이 자기 색을 이은 뒤 펜이 마지막으로 들어간 칸이면 X로 적는다.

해가 여러 개일 수 있다. 그중 사전순으로 가장 작은 것을 출력한다. 출력할 $N$개의 줄을 위에서 아래로 이어 붙여 길이 $N^2$인 문자열로 보고, 문자의 크기는 D, L, R, U, X 차례로 커진다고 보고 비교한다.