H1. Cool Swap Walk (Easy Version)
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

This is the easy 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 $$$2n+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 2n+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.
Example
Input
3
2
1 2
3
2 1 3
4
3 2 3 4
Output
0
2
RRDD
DRDR
3
RRDRDD
DRDDRR
DDRRRD
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.