Alice 有一个包含 $$$2$$$ 行和 $$$n$$$ 列的网格。她使用大小为 $$$1 \times 2$$$ 的 $$$n$$$ 多米诺骨牌完全覆盖网格 - Alice 可以将它们垂直或水平放置,并且每个单元格都应该被一个多米诺骨牌覆盖。
现在,她决定向鲍勃展示网格的一行。帮助鲍勃找出网格的另一行是什么样子!
输入
输入由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 5000$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 100$$$) — 网格的宽度。
每个测试用例的第二行包含一个由 $$$n$$$ 字符组成的字符串 $$$s$$$,每个字符都是 L、R、U 或 D,分别代表多米诺骨牌的左半部分、右半部分、上半部分或下半部分(请参阅注释以更好地理解)。该字符串代表网格的其中一行。
对输入的附加约束:每个输入对应于至少一个有效的平铺。
输出
对于每个测试用例,输出一个字符串 - 网格的另一行,使用与输入字符串相同的格式。如果有多个答案,请打印其中一个。
示例
输入 #1
4 1 U 2 LR 5 LRDLR 6 UUUUUU
输出 #1
D LR LRULR DDDDDD
注意
在第一个测试用例中,Alice 向 Bob 展示了顶行,整个网格可能如下所示:
在第二个测试用例中,Alice 向 Bob 展示了底行,整个网格可能如下所示:
在第三个测试用例中,Alice 向 Bob 展示了底行,整个网格可能如下所示:
在第四个测试用例中,Alice 向 Bob 显示了顶行,整个网格可能如下所示: