Description

八数码，也叫作“九宫格”，来自一个 古老的游戏。在这个游戏中，你将得到一个$3×$$3$的棋盘和$8$个方块。方 块的编号为$1～8$，其中一块方块丢失，称之为“X”。“X”可与相邻的 方块交换位置。用符号“r”表示将“X”与其右侧的方块进行交换， 用“l”表示左侧的方块，用“u”表示其上方的方块，用“d”表示其 下方的方块。

棋盘的状态可以用字符串$S$表示，使用下面显示的规则。

问题是使用“r”“u”“l”“d”操作列表可以将棋盘的状态从状 态$A$转到状态$B$，需要找到满足以下约束的结果：

（1）在所有可能的解决方案中，它的长度最小；

（2）它是所有最小长度解中词典序最小的一个。

Format

Input

第$1$行是$T （T ≤200）$，表示测试用例数。每个测试用例 的输入都由两行组成，状态$A$位于第$1$行，状态$B$位于第$2$行。保证从状态 $A$到状态$B$都有有效的解决方案。

Output

对于每个测试用例，都输出两行。第$1$行是“Case x :d ”格式，其中$x$是从$1$开始计算的案例号，$d$是将$A$转换到$B$的操作列表 的最小长度。第$2$行是满足约束条件的操作列表。

Samples

3
24183756X
37216X548
X37814526
237X81645
87416523X
38612754X

Case 1: 23
lluruldrdlurruldrdllurr
Case 2: 19
rddlurdrululddrrull
Case 3: 18
uulddlurdruullddrr