Пташине дерево
Пташине дерево — це нескінченне бінарне дерево, яке на перших 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.
Вихідні дані
Для кожного тесту виведіть в окремому рядку рядкове представлення розташування цього дробу в дереві птахів.