Bird tree#4009
The Bird tree is an infinite binary tree, whose first levels look as follows:
It can be defined as follows:
This is a co-recursive definition in which both occurrences of refer to the full (infinite) tree. The expression bird + 1 means that is added to every fraction in the tree, and means that every fraction in the tree is inverted (so becomes ).
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, 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.
The first line contains the number of test cases, at most . Each test case is one line with two integers and (1 \leq a, b \leq 10^9), separated by a '/'. These represent the numerator and denominator of a reduced fraction. The integers and are not both equal to , and they satisfy \gcd(a, b) = 1.
For every test case the length of the string with directions will be at most .
For each test case print one line with the string representation of the location of this fraction in the Bird tree.
Example 1