Cho hai phân số ~\frac{0}{1}~ và ~\frac{1}{0}~. Ta tạo ra dãy vô hạn bằng cách: xét hai phân số ~\frac{a}{b}~ và ~\frac{c}{d}~ đang ở cạnh nhau, ta thêm phân số ~\frac{a\ +\ c}{b\ +\ d}~ vào vị trí giữa. Dãy số có thể tạo ra cây nhị phân vô hạn đầy đủ như hình minh hoạ:

Ta lần lượt sử dụng ~L~ và ~R~ thể hiện việc đi sang cây con trái và cây con phải khi đi từ gốc ~\frac{1}{1}~. trungnotchung có ~q~ thắc mắc bấy lâu nay: tìm đường đi ngắn nhất giữa hai phân số ~\frac{1}{1}~ và ~\frac{x}{y}~.

Input

• Dòng đầu tiên nhập số nguyên dương ~q~ ~(1 \le q \le 100)~ - số câu hỏi của bạn Trung.

• Dòng thứ ~i~ trong ~q~ dòng tiếp theo chứa hai số nguyên dương ~(x_i, y_i)~ trong câu hỏi thứ ~i~ mà bạn Trung đưa ra. Dữ liệu đảm bảo luôn có ít nhất một đường đi giữa hai phân số ~\frac{1}{1}~ và ~\frac{x_i}{y_i}~ ~(x_i, y_i \le 9 \times 10^{18},\ max(x_i, y_i) > 1,\ gcd(x_i, y_i) = 1)~.

Output

• In ra ~q~ dòng là đáp án của các câu hỏi.

Subtask

• ~20\%~ số test có độ dài xâu kết quả không vượt quá ~17~.

• ~70\%~ số test có ~x_i, y_i \le 10^9~.

• ~10\%~ số test không có ràng buộc gì thêm.

Sample Input 1

2
5 7
878 323

Sample Output 1

LRRL
RRLRRLRLLLLRLRRR

Notes

Ở testcase đầu tiên, đường đi ngắn nhất là ~\frac{1}{1}~ ~\stackrel{L}{\rightarrow}~ ~\frac{1}{2}~ ~\stackrel{R}{\rightarrow}~ ~\frac{2}{3}~ ~\stackrel{R}{\rightarrow}~ ~\frac{3}{4}~ ~\stackrel{L}{\rightarrow}~ ~\frac{5}{7}~.