Թաքցված խնդիր
|Այս խնդիրը թաքցված է խմբագրական խրհրդի անդամի կողմից քանի որ կամ այն ոչ ճիշտ լեզվով է գրված,|կամ թեստային տվյալներն են սխալ, կամ խնդրի ձևակերպումը պարզ չէ։|

ACM_0057 - DECODING THE HALLWAY

   Edward is now 21 years old. He has to appear in an exam to renew his State Alchemist title. This year the exam is arranged in a bit different way. There will be a long hallway. Each alchemist will enter the hallway from the left side and come out from the right side and he has to do this n times. During this tour they have to bend the hallway segments right-left alternatively. Let’s describe the process in some pictures:

  • First time (First picture): Initially, the hallway is a straight line (soft line in the first picture). So alchemist will bend this segment to right side (he is going from left to right) like the hard line in the first picture above.
  • Second time (Second picture): Now he will find two segments in hallway (like soft line in picture). So he will bend the first hallway to right, second one to left (like the hard lines).
  • Third time (Third picture): Now he will find four segments in the hallway (like the soft lines) and he will bend them to Right, Left, Right and Left respectively.
  • And this goes on for fourth and fifth times in the picture.

   Since Full Metal Alchemist Edward is so good, he did it perfectly. Now it is turn of the judges to check the bending if it is correct or not. The judge enters at the left end and comes out from the right end. But during his travel he notes down the turning, R for Right and L for Left. So if n = 1, then the judge would have noted down L. If n = 2, it would have been LLR. For n = 4, it would have been: LLRLLRRLLLRRLRR.

   Since this string will grow exponentially with n, it will be tough to check whether the bending is correct or not. So the judges have some pre-generated strings and they know whether this string will appear as substring in the final string or not. Unfortunately the judges have lost the answer sheet, can you help them to recover it?

Input

   First line of the test file contains a positive integer T denoting number of test cases (T <= 105). Hence follows T lines, each containing an integer and a string: n S. n is the number of times Edward has passed through the hallway; and S is the string the judge is going to check with. You may assume that S consists of only the letters L and R. (n <= 1000, length of <= 100).  Also you may assume that length of S will not be greater than the length of the string for n.

Output

   For each test case output the case number and Yes or No denoting whether the string is in the final string as substring.

Examples

stdin

stdout

1

2

1 R

4 LRRLL

Case 1: No

Case 2: Yes


Ավելացրեց.Հրանտ Հովհաննիսյան
Ամսաթիվ.2013-12-30
Ժամանակի սահմանափակումը.1s
Ծրագրի տեքստի սահմանափակումը.50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Լեզուներ.Բոլորը բացի ASM32 ASM64 GAWK CLPS CLOJURE D ERL FSHARP FORTRAN GOSU HASK ICON ICK NEM NIM OBJC-CLANG PICO PIKE PYPY PYPY3 PY_NBC RUST SCM guile CHICKEN SED TCL WHITESPACE
Աղբյուրը.SWERC 2013.D

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.