DSLR

There is a simple calculator that uses four commands: $D$, $S$, $L$, and $R$. The calculator has a single register that stores a decimal number $n$ with $0 \le n < 10000$. Each command transforms the value $n$ currently in the register. Let the four digits of $n$ be $d_1, d_2, d_3, d_4$, so that $n = ((d_1 \times 10 + d_2) \times 10 + d_3) \times 10 + d_4$.

• D: doubles $n$. If the result is greater than $9999$, it is reduced modulo $10000$; that is, the register receives $2n \bmod 10000$.
• S: stores $n - 1$. If $n$ is $0$, it stores $9999$ instead.
• L: rotates the four digits of $n$ one place to the left. Afterwards the digits, from the left, are $d_2, d_3, d_4, d_1$.
• R: rotates the four digits of $n$ one place to the right. Afterwards the digits, from the left, are $d_4, d_1, d_2, d_3$.

$L$ and $R$ always rotate over four decimal digits. For example, if $n = 1234$, then $L$ gives $2341$ and $R$ gives $4123$.

Given two distinct integers $A$ and $B$ ($A \ne B$), write a program that finds the shortest command string that turns $A$ into $B$. For example, if $A = 1234$ and $B = 3412$, two commands suffice in either of these ways:

• apply $L$ twice: $1234 \to 2341 \to 3412$
• apply $R$ twice: $1234 \to 4123 \to 3412$

Here the two shortest command strings are LL and RR, and you must output LL, which comes first in alphabetical order.

Be careful when a digit is $0$. For example, applying $L$ to $1000$ gives $0001$, so the result is $1$; applying $R$ gives $0100$, so the result is $100$.

The first line contains the number of test cases $T$. Each of the next $T$ lines contains two integers $A$ and $B$ separated by a space, where $A$ is the register's initial value and $B$ is the target value. Both satisfy $0 \le A, B < 10000$ and $A \ne B$.

For each test case, print on its own line the shortest command string that turns $A$ into $B$. If several command strings share the minimum length, print the lexicographically smallest one, comparing command letters in alphabetical order $D < L < R < S$.