Decoding the Hallway

Edward is 21 now. To renew his State Alchemist title he has to pass an exam, and this year the exam is held in a long hallway. Each alchemist enters at the left end, comes out at the right end, and repeats the walk $n$ times.

On every walk the alchemist folds the hallway segments he meets, alternating right, left, right, left in the order he meets them. Folding one segment creates a single turn there and splits that segment in two.

• On the first walk the hallway is one straight segment, so he folds that segment to the right.
• On the second walk there are two segments. He folds the first one to the right and the second one to the left.
• On the third walk there are four segments, folded right, left, right, left in that order.
• The fourth and fifth walks continue the same way.

The $k$-th walk meets $2^{k-1}$ segments, so after $n$ walks the hallway has $2^n - 1$ turns.

Edward finished without a single mistake. Now a judge checks the folding. The judge also enters at the left end and comes out at the right end, writing down every turn he passes, R for a right turn and L for a left turn. A fold direction is not written down as is, so use these four records as the reference:

• $n = 1$: L
• $n = 2$: LLR
• $n = 3$: LLRLLRR
• $n = 4$: LLRLLRRLLLRRLRR

The record grows exponentially with $n$, which makes checking it by hand hard. The judges therefore prepared some strings in advance and worked out for each one whether it appears in the final record as a substring. Then they lost that answer sheet. Help them get it back.

The first line contains the number of test cases $T$. ($1 \le T \le 10^5$)

Each of the next $T$ lines contains an integer $n$ and a string $S$ separated by a space. $n$ is the number of times Edward walked the hallway and $S$ is the string the judge wants to check. $S$ consists only of the letters L and R. ($1 \le n \le 1000$, $1 \le |S| \le 100$)

The length of $S$ is never greater than the length of the record for $n$.

For each test case print one line, Case x: Yes or Case x: No, where $x$ is the test case number starting from 1. Print Yes when $S$ appears as a substring of the record of the hallway after $n$ walks, and No otherwise.