Rotation Maze

You are given a maze described by a 2D grid of cells. Each cell is one of: an empty space, a wall, the starting point, or the ending point.

A ball begins at the starting point. Gravity pulls the ball toward the bottom of the grid: the ball keeps falling straight down until a wall is directly beneath it. If nothing is beneath it, the ball falls off the board and is lost.

You may perform two operations on the maze:

• L — rotate the entire maze 90° to the left (counter-clockwise).
• R — rotate the entire maze 90° to the right (clockwise).

After every rotation, gravity acts again and the ball falls until it is supported or drops off the board. A solution is a string of L and R characters that brings the ball to rest on the ending point. If no such sequence exists, the answer is NONE.

Rules:

1. The ball may pass through the starting and ending points. It must come to rest on the ending point to count as a solution; merely rolling through the ending point does not count.
2. The starting and ending points are not required to lie on the border of the board.
3. The maze need not be completely enclosed, so the ball may fall off the board (once it does, it is lost).
4. If more than one sequence of rotations works, output the shortest one. If several sequences are equally short, output the one that comes first alphabetically (L before R).
5. The board starts in the orientation given in the input, with gravity acting downward. Before any rotation is applied, the ball first falls from its starting cell as far as it can.

If the ball already rests on the ending point before any rotation, the sequence is empty.

The first line contains the number of test cases $T$ ($1 \le T \le 20$). The test cases follow one after another.

Each test case begins with a line containing two integers nx and ny, the number of columns and the number of rows of the maze, respectively. The next ny lines each contain nx characters describing one row of the maze:

• . is an empty cell the ball can roll over.
• s is the starting point of the ball.
• e is the ending (goal) point.
• Any other character is a wall the ball cannot pass through.

For each test case, print one line in the form Case i: X, where i is the test case number (starting from 1) and X is the sequence of rotations that solves the maze.

Output the shortest valid sequence; if several are equally short, output the alphabetically first one. If the maze cannot be solved, output NONE in place of the sequence.