“Connect the Cells” 是一个非常著名的游戏，你可以在任何移动设备上找到它的版本。

该游戏在一个 $N$ 行 $N$ 列的棋盘上进行。每个单元格要么是空的，要么是带颜色的。我们用 ‘0’ 表示空单元格，用 ‘1’ 到 ‘9’ 的数字表示带颜色的单元格。对于棋盘上存在的每种颜色，恰好有两个该颜色的单元格。你的任务是将每一对相同颜色的单元格连接起来，且不能留下任何空单元格。

如果两个单元格共享一条边（垂直或水平），则它们相邻。输入网格中相同颜色的单元格永远不会相邻。

连接两个相同颜色单元格的方法如下：假设你为每种颜色准备了一支笔，一旦笔触碰到任何单元格，它就会将其涂色。你将从两个单元格中的一个开始放置笔，并将其从当前单元格移动到另一个相邻的空单元格，直到最终移动到该颜色的第二个单元格。一旦笔进入该颜色的第二个单元格，这两个单元格即被视为已连接，你应该停止使用这支笔，并开始连接其他颜色（如果还有剩余的话）。笔不能离开棋盘，也不能对同一个单元格涂色超过一次。

唯一的例外是笔可以处于已经涂色的单元格上，即当它处于其颜色的起始单元格或结束单元格时，且它只能在这些单元格上各停留一次。

你能编写一个程序来解决这个游戏吗？

输入格式

你的程序将在一个或多个测试用例上进行测试。输入的第一行是一个整数 $T$ ($1 \le T \le 100$)，表示测试用例的数量。接下来是 $T$ 个测试用例。每个测试用例的第一行包含一个整数 $N$ ($3 \le N \le 8$)，表示棋盘的大小。随后是 $N$ 行，每行包含 $N$ 个数字。每个数字代表一个单元格，‘0’ 表示空单元格。保证每个测试用例至少有一个有效的解决方案，并且所有输入棋盘都满足上述所有条件。

对于每个测试用例，如果棋盘包含 $X$ 种不同的颜色，它们将使用从 1 到 $X$ 的数字命名（每个测试用例至少有一种颜色，最多有 9 种颜色）。

输出格式

对于每个测试用例，打印一行 “Case n:”（不含引号），其中 $n$ 是测试用例编号（从 1 开始），随后打印 $N$ 行，每行应包含 $N$ 个字符。第 $i$ 行的第 $j$ 个字符表示你从网格中第 $i$ 行第 $j$ 个单元格离开时所使用的方向（‘U’ 表示向上，‘R’ 表示向右，‘D’ 表示向下，‘L’ 表示向左，如果这是连接该颜色单元格后进入的最后一个单元格，则为 ‘X’）。如果存在多个解决方案，打印其中任意一个即可。

样例

输入 1

2
3
100
001
202
3
101
000
000

输出 1

Case 1:
RRD
RDX
URX
Case 2:
DRX
DUL
RRU

说明

以下是两个样例的情况：

First Case

Second Case

以下是每个样例的一种有效解决方案：

First Case

Second Case