eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Птичье дерево

Птичье дерево

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

Птичьим называется бесконечное бинарное дерево, 5 уровней которого выглядят следующим образом:

prb4009-01

Оно может быть определено следующим образом:

prb4009-02

Это так называемое ко-рекурсивное определение, в котором оба вхождения bird относятся к полному (бесконечному) дереву. Выражение bird + 1 означает что 1 прибавляется к каждой дроби дерева, а 1 / bird означает что каждая дробь в дереве инвертируется (то есть a / b становится b / a).

Удивительно, но дерево содержит каждое положительное рациональное число ровно один раз, поэтому каждая несократимая дробь находится в уникальном месте дерева. Следовательно, мы можем описать рациональное число, задав направления (L для левого поддерева, R для правого поддерева) в дереве птиц. Например, 2 / 5 представлены как LRR. По заданной несократимой дроби выведите строку, состоящую из L и R: направлений, по которым можно найти эту дробь начиная с вершины дерева.

Вхідні дані

Первая строка содержит количество тестов, не более 100. Каждый тест представлен одной строкой, содержащей два целых числа a и b (1a, b10^9), разделенных с помощью '/'. Они представляют собой числитель и знаменатель несократимой дроби. Оба целых числа a и b не равны 1 и удовлетворяют условию НОД (a, b) = 1.

Для каждого теста длина строки с направлениями будет не более 10000.

Вихідні дані

Для каждого теста выведите в отдельной строке строковое представление расположения этой дроби в дереве птиц.

Приклад

Вхідні дані #1
3
1/2
2/5
7/3
Вихідні дані #1
L
LRR
RLLR
Джерело 2011 ACM NWERC