Птичье дерево
Птичьим называется бесконечное бинарное дерево, 5 уровней которого выглядят следующим образом:
Оно может быть определено следующим образом:
Это так называемое ко-рекурсивное определение, в котором оба вхождения bird относятся к полному (бесконечному) дереву. Выражение bird + 1 означает что 1 прибавляется к каждой дроби дерева, а 1 / bird означает что каждая дробь в дереве инвертируется (то есть a / b становится b / a).
Удивительно, но дерево содержит каждое положительное рациональное число ровно один раз, поэтому каждая несократимая дробь находится в уникальном месте дерева. Следовательно, мы можем описать рациональное число, задав направления (L для левого поддерева, R для правого поддерева) в дереве птиц. Например, 2 / 5 представлены как LRR. По заданной несократимой дроби выведите строку, состоящую из L и R: направлений, по которым можно найти эту дробь начиная с вершины дерева.
Входные данные
Первая строка содержит количество тестов, не более 100. Каждый тест представлен одной строкой, содержащей два целых числа a и b (1 ≤ a, b ≤ 10^9), разделенных с помощью '/'. Они представляют собой числитель и знаменатель несократимой дроби. Оба целых числа a и b не равны 1 и удовлетворяют условию НОД (a, b) = 1.
Для каждого теста длина строки с направлениями будет не более 10000.
Выходные данные
Для каждого теста выведите в отдельной строке строковое представление расположения этой дроби в дереве птиц.