A Foldy but a Goody

Suppose you have a strip of paper and may fold it in one of two ways:

• an upper fold, where the right end of the paper is brought over the top of the left end; and
• a lower fold, where the right end of the paper is brought below the left end.

The diagram below illustrates both kinds of folds.

After folding the strip several times, you unfold it again, opening every crease to a right angle of $90^\circ$. The example below shows an upper fold, followed by a lower fold, and then the unfolding.

Place the left end of the folded strip at the origin $(0,0)$ and the first right angle at $(1,0)$. It is natural to ask: where is the second right angle? The third? Where does the other end of the strip come to rest? Given a sequence of folds and an index, report the location of the chosen point.

The first line contains an integer $T$, the number of test cases.

Each of the next $T$ lines describes one test case: a string of the letters U and L, giving a series of upper and lower folds, followed by an integer $m$. The length of the string is between $1$ and $30$ inclusive.

If the string describes $n$ folds, the unfolded strip is made of $2^n$ unit segments, so the two ends and all right angles occupy the positions $0, 1, \dots, 2^n$. The value $m$ chooses one of them:

• $m = 0$ is the left end, located at $(0,0)$;
• $m = 2^n$ is the right end of the strip;
• any $m$ with $1 \le m \le 2^n - 1$ is a right angle, counted from the left ($m = 1$ is the first right angle, and so on).

For each test case, print one line giving the location of the requested right angle or end point, written as (x,y): an opening parenthesis, the integer $x$, a comma with no surrounding spaces, the integer $y$, and a closing parenthesis.

Assume that when there are $n$ folds the strip has length $2^n$, so the distance between adjacent creases is exactly $1$ unit.