Imbalance Obviation

You have a special balance scale with two pans, left and right, both initially empty. You also have a box of identical 1-gram marbles. There are N of these marbles, numbered from 1 to N.

The scale is very sensitive: if the total weight on the left pan and the total weight on the right pan ever differ by strictly more than 1 gram, the scale breaks. For example, if at some point one pan holds 4 marbles, the other pan must hold 3, 4, or 5 marbles.

Your friend Libra has challenged you to do the following without breaking the scale at any point:

• First, put all of the marbles on the scale one at a time, in numerical order: marble 1, then marble 2, and so on up to marble N. For each marble, you choose whether to place it on the left pan or on the right pan.
• Then, remove all of the marbles from the scale one at a time, in an order A1, A2, ..., AN chosen by your friend. This order is a permutation of 1, 2, ..., N. The i-th marble you remove must be the marble numbered Ai.

Find a way to do this.

The first line of the input gives the number of test cases, T. T test cases follow. Each test case begins with a line containing an integer N, the number of marbles. The next line contains N integers A1, A2, ..., AN, which form a permutation of the first N natural numbers. The marble numbered Ai must be the i-th marble you remove in the removal phase.

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is a string of N characters. The i-th character (counting from 1) is uppercase L if the marble numbered i is put on the left pan, or uppercase R if it is put on the right pan.

It is guaranteed that at least one answer exists. If there are multiple valid answers, output the lexicographically smallest one, where L comes before R.

• 1 ≤ T ≤ 100
• 1 ≤ N
• The sum of N over all test cases in one input is at most 200,000.
• 1 ≤ Ai ≤ N for all i.
• Ai ≠ Aj for all i ≠ j.

In the first sample test case, put marble 1 on the left pan, then marble 2 on the right pan, then marble 3 on the right pan, then marble 4 on the left pan. The total weights on the (left, right) pans go through (1, 0), (1, 1), (1, 2), and (2, 2), and never differ by more than 1.

Then the marbles must be removed in the order 3, 1, 2, 4. Again, the total weights go through (2, 1), (1, 1), (1, 0), and (0, 0), and never differ by more than 1. The challenge succeeds.

By the same reasoning with the two pans swapped, RLLR also keeps the scale intact, but LRRL is lexicographically smaller, so the answer is LRRL.

The following answers break the scale for this test case:

• LLRR: breaks the scale when placing marble 2.
• LRLR: breaks the scale when removing marble 1 (the second marble to be removed).

Here are some examples with odd N:

• For the order 1, both L and R keep the scale intact, so the answer is L.
• For the order 2 3 1, LRR and RLL are the only valid answers, so the answer is LRR. LLL, LLR, RRL, and RRR break the scale during the placement phase. LRL and RLR break the scale during the removal phase.