This is the hard version of the problem. The only difference is the maximum number of operations you can perform. You can only make hacks if both versions are solved.

You are given an array $a$ of size $n$.

A cool swap walk is the following process:

• In an $n \times n$ grid, we note the cells in row $i$ and column $j$ as $(i, j)$. You need to walk from $(1,1)$ to $(n,n)$, taking only steps to the right or down.
• Formally, if you are in $(x,y)$ currently, you can step to either $(x+1,y)$ or $(x,y+1)$, but you can not step beyond the boundaries of the grid.
• When you step in $(i,j)$, you must swap $a_i$ and $a_j$ when $i \neq j$.

You can perform at most $n+4$ cool swap walks. Sort the array $a_1, a_2, \ldots, a_n$ in non-decreasing order. We can show that it's always possible to do so.

Input

The first line contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The first line of each test case contains an integer $n$ ($2 \leq n \leq 500$) — the size of the array.

The second line of each test case contains $n$ integers $a_1,a_2,\ldots ,a_n$ ($1 \le a_i \le n$) — the elements of the array.

It is guaranteed that the sum of $n^2$ over all test cases does not exceed $2.5 \cdot 10^5$.

Output

For each test case, your output should consist of several lines:

• The first line contains an integer $k$ ($0 \leq k \leq n+4$), representing the number of cool swap walks you perform.
• Each of the next $k$ lines contains a string $s$ of length $2n-2$ consisting only of R and D, representing the path (letters are case sensitive). For all $1 \le i \le 2n-2$, if $s_i=$ R, you walk right in the $i$-th step, otherwise you walk down in the $i$-th step.

Note

In the first test case, the array $a$ is already non-decreasing, so you don't need to perform any walk.

In the second test case, $a=[2,1,3]$ initially.

In the first walk:

• In the $1$-st step, you step right to $(1,2)$. Then, $a=[1,2,3]$. Note that although the array $a$ is already non-decreasing, you can not stop until you reach $(n,n)$.
• In the $2$-nd step, you step right to $(1,3)$. Then, $a=[3,2,1]$.
• In the $3$-rd step, you step down to $(2,3)$. Then, $a=[3,1,2]$.
• In the $4$-th step, you step down to $(3,3)$. Then, $a=[3,1,2]$.

In the second walk:

• In the $1$-st step, you step down to $(2,1)$. Then, $a=[1,3,2]$.
• In the $2$-nd step, you step right to $(2,2)$. Then, $a=[1,3,2]$.
• In the $3$-rd step, you step down to $(3,2)$. Then, $a=[1,2,3]$.
• In the $4$-th step, you step down to $(3,3)$. Then, $a=[1,2,3]$.

After the two cool swap walks above, we get $a=[1,2,3]$, which is non-decreasing.