DSLR

네 개의 명령어 $D$, $S$, $L$, $R$ 을 사용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있으며, 레지스터에는 $0$ 이상 $10000$ 미만의 십진수를 저장할 수 있다. 각 명령어는 레지스터에 저장된 수 $n$ 을 아래와 같이 바꾼다. $n$ 의 네 자리 숫자를 각각 $d_1, d_2, d_3, d_4$ 라 하자. 즉 $n = ((d_1 \times 10 + d_2) \times 10 + d_3) \times 10 + d_4$ 이다.

• D: $n$ 을 두 배로 만든다. 결과가 $9999$ 보다 크면 $10000$ 으로 나눈 나머지를 취한다. 즉 $2n \bmod 10000$ 을 레지스터에 저장한다.
• S: $n$ 에서 $1$ 을 뺀 $n-1$ 을 저장한다. 단, $n$ 이 $0$ 이면 $9999$ 를 저장한다.
• L: $n$ 의 네 자리 숫자를 왼쪽으로 한 칸 회전시킨 결과를 저장한다. 연산 후 네 자리 숫자는 왼쪽부터 $d_2, d_3, d_4, d_1$ 이 된다.
• R: $n$ 의 네 자리 숫자를 오른쪽으로 한 칸 회전시킨 결과를 저장한다. 연산 후 네 자리 숫자는 왼쪽부터 $d_4, d_1, d_2, d_3$ 이 된다.

$L$ 과 $R$ 은 항상 네 자리 십진수를 기준으로 회전한다. 예를 들어 $n = 1234$ 이면 $L$ 을 적용한 결과는 $2341$, $R$ 을 적용한 결과는 $4123$ 이다.

서로 다른 두 정수 $A$ 와 $B$ ($A \ne B$) 가 주어질 때, $A$ 를 $B$ 로 바꾸는 가장 짧은 명령어 문자열을 구하는 프로그램을 작성한다. 예를 들어 $A = 1234$, $B = 3412$ 이면 다음 두 방법으로 각각 두 번의 명령어만에 바꿀 수 있다.

• $L$ 을 두 번: $1234 \to 2341 \to 3412$
• $R$ 을 두 번: $1234 \to 4123 \to 3412$

이 경우 길이가 가장 짧은 명령어 문자열은 LL 과 RR 두 가지이며, 사전순으로 더 앞서는 LL 을 출력해야 한다.

자릿수에 $0$ 이 포함될 때를 주의한다. 예를 들어 $1000$ 에 $L$ 을 적용하면 $0001$ 이 되어 결과는 $1$ 이고, $R$ 을 적용하면 $0100$ 이 되어 결과는 $100$ 이다.

첫 줄에 테스트 케이스의 개수 $T$ 가 주어진다. 이어지는 $T$ 개의 줄에 각 테스트 케이스가 주어지며, 각 줄에는 두 정수 $A$ 와 $B$ 가 공백으로 구분되어 주어진다. $A$ 는 레지스터의 초기 값, $B$ 는 목표 값이며, 둘 다 $0$ 이상 $10000$ 미만이고 $A \ne B$ 이다.

각 테스트 케이스마다 $A$ 를 $B$ 로 바꾸는 데 필요한 가장 짧은 명령어 문자열을 한 줄에 하나씩 출력한다. 길이가 최소인 명령어 문자열이 여러 개라면, 그중 사전순으로 가장 앞서는 것을 출력한다. 명령어 문자는 알파벳 순서, 즉 $D < L < R < S$ 로 비교한다.