Пташине дерево#4009

Пташине дерево

1 секунда

128 мегабайтів

Середня

Пташине дерево — це нескінченне бінарне дерево, яке на перших $5$ рівнях виглядає так:

Його можна описати наступним чином:

Це так зване ко-рекурсивне визначення, де обидва входження bird відносяться до повного (нескінченного) дерева. Вираз $bi r d + 1$ bird + 1 означає, що $1$ додається до кожного дробу дерева, а $1/ bi r d$ означає, що кожен дріб у дереві інвертується (тобто $a / b$ стає $b / a$ ).

Цікаво, що дерево містить кожне додатне раціональне число рівно один раз, тому кожен нескоротний дріб займає унікальне місце в дереві. Таким чином, ми можемо описати раціональне число, вказавши напрямки (L для лівого піддерева, R для правого піддерева) у дереві птахів. Наприклад, $2/5$ представлено як LRR. Для заданого нескоротного дробу виведіть рядок, що складається з L і R: напрямків, за якими можна знайти цей дріб, починаючи з вершини дерева.

Вхідні дані

Перший рядок містить кількість тестів, не більше $100$ . Кожен тест представлений одним рядком, що містить два цілі числа $a$ і $b$ ( $1 \leq a, b \leq 1 0^{9}$ 1 \leq a, b \leq 10^9), розділених символом '/'. Вони представляють чисельник і знаменник нескоротного дробу. Цілі числа $a$ і $b$ не можуть одночасно дорівнювати $1$ і задовольняють умову $НСД (a, b) = 1$ \text{НСД}(a, b) = 1.

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

Вихідні дані

Для кожного тесту виведіть в окремому рядку рядкове представлення розташування цього дробу в дереві птахів.

Приклади

Приклад 1