F. Following Arrows
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Panda is a puzzle designer and decides to create a two-dimensional maze based on an arrow-following theme. This maze is a grid with $$$N$$$ rows and $$$M$$$ columns. Each cell contains an arrow: $$$\texttt{L}$$$ (Left), $$$\texttt{R}$$$ (Right), $$$\texttt{U}$$$ (Up), or $$$\texttt{D}$$$ (Down).

Cells are indexed with $$$(x,y)$$$, where $$$x$$$ is the row $$$(1 \le x \le N)$$$ and $$$y$$$ is the column $$$(1 \le y \le M)$$$. The top-left corner is $$$(1,1)$$$ and the bottom-right corner is $$$(N,M)$$$. The player starts at position $$$(1,1)$$$, and proceeds in discrete steps until reaching $$$(N,M)$$$ for the first time. Each step consists of the following two actions performed in order:

  1. Move: Move one step in the direction of the arrow in your current cell. You only remain in your current cell if the attempted move would take you outside the maze.
  2. Flip: After the move (or non-move) from step 1, the arrow in the cell where you were before the move changes to its opposite direction (i.e., change $$$\texttt{L}$$$ to $$$\texttt{R}$$$, $$$\texttt{R}$$$ to $$$\texttt{L}$$$, $$$\texttt{U}$$$ to $$$\texttt{D}$$$, and $$$\texttt{D}$$$ to $$$\texttt{U}$$$). If you didn't move, you flip the arrow in your current cell.

Panda wants to design a maze, with a maximum size of $$$8 \times 8$$$, such that a player starting at $$$(1,1)$$$ and following the rules reaches $$$(N,M)$$$ in exactly $$$k$$$ steps.

Input

The first line contains an integer $$$T$$$ ($$$1 \leq T \leq 2\times 10^4$$$), denoting the number of test cases.

Each test case contains an integer $$$k$$$ ($$$1 \leq k \leq 10^6$$$) in a single line, which is the required number of steps for the player to exit the maze.

It is guaranteed that the sum of $$$k$$$ over all the test cases does not exceed $$$8\times 10^7$$$.

Output

For each test case, if it is impossible to design such a maze, output $$$\texttt{-1 -1}$$$ in a single line. Otherwise, first output one line containing two integers $$$N,M$$$ ($$$1 \leq N, M \leq 8$$$), representing the size of the maze. Then output $$$N$$$ lines, with $$$M$$$ characters per line, representing the maze. Every character in the maze is one of $$$\texttt{L}$$$, $$$\texttt{R}$$$, $$$\texttt{U}$$$, $$$\texttt{D}$$$. You must ensure that the number of operations required to go from $$$(1,1)$$$ to $$$(N,M)$$$ is exactly $$$k$$$.

Example
Input
5
1
4
9
16
25
Output
1 2
RR
2 2
LU
RD
3 2
LU
DR
LL
3 2
LU
UR
LL
1 6
LLRLLR