eolymp
bolt
Try our new interface for solving problems
Problems

Bird tree

Bird tree

Time limit 1 second
Memory limit 128 MiB

The Bird tree is an infinite binary tree, whose first 5 levels look as follows:

prb4009-01

It can be defined as follows:

prb4009-02

This is a co-recursive definition in which both occurrences of bird refer to the full (infinite) tree. The expression bird + 1 means that 1 is added to every fraction in the tree, and 1 / bird means that every fraction in the tree is inverted (so a / b becomes b / a).

Surprisingly, the tree contains every positive rational number exactly once, so every reduced fraction is at a unique place in the tree. Hence, we can also describe a rational number by giving directions (L for left subtree, R for right subtree) in the Bird tree. For example, 2/5 is represented by LRR. Given a reduced fraction, return a string consisting of L’s and R’s: the directions to locate this fraction from the top of the tree.

Input data

The first line contains the number of test cases, at most 100. Each test case is one line with two integers a and b (1a, b10^9), separated by a '/'. These represent the numerator and denominator of a reduced fraction. The integers a and b are not both equal to 1, and they satisfy gcd(a, b) = 1.

For every test case the length of the string with directions will be at most 10000.

Output data

For each test case print one line with the string representation of the location of this fraction in the Bird tree.

Examples

Input example #1
3
1/2
2/5
7/3
Output example #1
L
LRR
RLLR
Source 2011 ACM NWERC