H2. 酷炫交换行走（困难版）
每次测试时间限制：2 秒
每次测试内存限制：256 MB

这是该问题的困难版本。唯一的区别在于你可以执行的最大操作次数。只有两个版本都解决的情况下，你才能进行 $hack$。

你有一个大小为 $n$ 的数组 $a$。

酷交换行走 定义如下：

在一个 $n \times n$ 的网格中，我们把第 $i$ 行第 $j$ 列的格子记为 $(i, j)$。你需要从 $(1, 1)$ 走到 $(n, n)$，每次只能向右或向下走一步。
形式化地说，如果你当前在 $(x, y)$，下一步可以走到 $(x+1, y)$ 或 $(x, y+1)$，但不能走出网格边界。
当你踏入格子 $(i, j)$ 时，如果 $i \neq j$，你必须交换 $a_i$ 和 $a_j$。

你可以执行最多 $n + 4$ 次酷交换行走。最终需要把数组 $a_1, a_2, \dots, a_n$ 按非降序排序。可以证明，这总是可行的。

输入
第一行包含一个整数 $t$（$1 \le t \le 10^4$）——测试用例的数量。
每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 500$）——数组的大小。
每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le n$）——数组中的元素。
保证所有测试用例的 $n^2$ 之和不超过 $2.5 \times 10^5$。

输出
对于每个测试用例，输出若干行：

• 第一行包含一个整数 $k$（$0 \le k \le n + 4$），表示你执行的酷交换行走的次数。
• 接下来的 $k$ 行，每行包含一个长度为 $2n - 2$ 的字符串 $s$，只包含字符 R 和 D，表示路径（字母区分大小写）。对于所有 $1 \le i \le 2n - 2$，如果 $s_i$ 是 R，表示第 $i$ 步向右走，否则表示第 $i$ 步向下走。

示例
输入

3
2
1 2
3
2 1 3
4
3 2 3 4

输出

0
2
RRDD
DRDR
3
RRDRDD
DRDDRR
DDRRRD

注意
在第一个测试用例中，数组 $a$ 已经非降序，因此不需要执行任何行走。

在第二个测试用例中，初始 $a = [2, 1, 3]$。

第一次行走：

• 第 $1$ 步：向右走到 $(1,2)$，此时 $a = [1, 2, 3]$。
• 第 $2$ 步：向右走到 $(1,3)$，此时 $a = [3, 2, 1]$。
• 第 $3$ 步：向下走到 $(2,3)$，此时 $a = [3, 1, 2]$。
• 第 $4$ 步：向下走到 $(3,3)$，此时 $a = [3, 1, 2]$。

第二次行走：

• 第 $1$ 步：向下走到 $(2,1)$，此时 $a = [1, 3, 2]$。
• 第 $2$ 步：向右走到 $(2,2)$，此时 $a = [1, 3, 2]$。
• 第 $3$ 步：向下走到 $(3,2)$，此时 $a = [1, 2, 3]$。
• 第 $4$ 步：向下走到 $(3,3)$，此时 $a = [1, 2, 3]$。

两次酷交换行走后，得到 $a = [1, 2, 3]$，已非降序。