Robots P16248

We have a board n × m where each square is marked with a S, L, R, or E. Initially, a robot is placed in any square, looking at the north (N), east (E), south (S) or west (W). Repeteadly, the robot does two operations:

• To turn or to explode:
  • If the robot is in a square marked with a L, it turns 90 degrees to the left;
  • If the robot is in a square marked with a R, it turns 90 degrees to the right;
  • If the robot is in a square marked with a S, it does not turn (it continues straight);
  • If the robot is in a square marked with an E, it explodes.
• Advance: The robot advances a square in the direction it is looking at (if it did not explode previously, of course).

Write a program that indicates if the robot will go out of the board, it will explode or it will be moving in the board forever.

Input

The input consists of a natural t ≥ 0 followed by t test data separated by a line in white. Each test data consists of a line with n and m (both of them between 1 and 60), followed by n lines with m characters (S, L, R, or E) each one. Finally, the last line of each test data contains the initial row (a number between 1 and n), and the initial direction (N, E, S or W).

Output

For each test data, your program must print “explodes”, “goes out”, or “does not go out” as required.