A Foldy but a Goody

You have a strip of paper and repeatedly fold it in one of two ways.

• Upper fold (U): bring the right end of the strip over onto the left end (folding it in half) so that the moved half lies on top.
• Lower fold (L): bring the right end of the strip onto the left end so that the moved half lies underneath.

After folding the strip several times, you unfold it again, opening every crease to a right angle (exactly 90 degrees). This turns the strip into a path made of unit-length segments joined at right angles.

Place the left end of the unfolded strip at the origin $(0,0)$, and let the first right angle be at $(1,0)$. Given the sequence of folds and a position along the paper, determine the coordinates of that position.

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

Each test case is a single line containing a string of the letters U and L, followed by an integer $m$. The string lists the folds in the order they are applied (from left to right), and its length $n$ satisfies $1 \le n \le 30$.

After $n$ folds and unfolding, the strip consists of $2^n$ unit segments separated by $2^n - 1$ right angles. The value $m$ selects a position on the paper:

• $m = 0$ is the left end, 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 end, $m = 1$ is the first right angle (at $(1,0)$), $m = 2$ the second, and so on.

For each test case, output one line of the form (x,y) giving the coordinates of the position selected by $m$.