ACEGAME - Game of 3 cards

no tags 

You come across an apparently respectable man on the street who makes you a seemingly legitimate proposition: the opportunity to play a game of Three Card Monte. He has a table with three face-up cards in a row: two jokers and one ace, with the ace in the middle. After you make a small wager, he turns the cards face-down and begins to manipulate the cards, swapping cards two at a time. After he completes the swaps, you are then to guess which card is the ace.

The series of card swaps will be given to you in order as a string swaps, containing only the characters 'L', 'R', 'E', and 'F'. Swaps[0] indicates the first swap. The 4 characters indicate the following moves:

  • L: swap the left and middle cards.
  • R: swap the right and middle cards.
  • E: swap the cards on the ends (the left and right cards).
  • F: fake swap (no cards actually change position).

Write a code that finds the final position of the ace, after all the swaps have been performed.

Input

First line of input consists of an integer T <= 50 which is the number of test cases. Each test case consists of a line containing the string of swaps. The line consists of atmost 50 characters where each character is either 'L', 'R', 'E' or 'F' with their meanings as defined above. Note that the line of swaps may be empty also.

Output

For each case, print "L" if the left card is the ace, "R" if the right card is the ace, and "M" if the ace is in the middle.

Example

Input:
5
L
REL
RFRFR

FLRELFLRELLFRLFEELFLRFLELRFLRFREFRFLLRFERLFLREFRFL

Output:
L
M
R
M
L


Added by:Mahesh Chandra Sharma
Date:2011-01-07
Time limit:0.100s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Based on a topcoder problem