회전 미로

2차원 격자로 표현된 미로가 주어집니다. 각 칸은 빈 칸, 벽, 시작점, 도착점 중 하나입니다.

공은 시작점에서 출발합니다. 중력은 공을 격자의 아래쪽으로 끌어당기며, 공은 바로 아래에 벽이 있을 때까지 계속 아래로 떨어집니다. 아래에 아무것도 없으면 공은 판 밖으로 떨어져 사라집니다.

미로에는 두 가지 연산을 적용할 수 있습니다.

• L — 미로 전체를 왼쪽(반시계 방향)으로 90° 회전합니다.
• R — 미로 전체를 오른쪽(시계 방향)으로 90° 회전합니다.

회전할 때마다 다시 중력이 작용하여, 공은 무언가에 받쳐지거나 판 밖으로 떨어질 때까지 낙하합니다. 해는 공을 도착점 위에 멈춰 세우는 L과 R의 문자열입니다. 그런 순서가 존재하지 않으면 답은 NONE입니다.

규칙:

1. 공은 시작점과 도착점을 지나갈 수 있습니다. 해가 되려면 공이 도착점 위에 멈춰 있어야 하며, 도착점을 그냥 굴러 지나가는 것은 인정되지 않습니다.
2. 시작점과 도착점이 반드시 판의 가장자리에 있을 필요는 없습니다.
3. 미로가 완전히 막혀 있을 필요는 없으므로 공이 판 밖으로 떨어질 수 있습니다(한 번 떨어지면 사라집니다).
4. 해가 되는 회전 순서가 여러 개이면 가장 짧은 것을 출력합니다. 가장 짧은 것이 여러 개이면 사전순으로 가장 앞서는 것을 출력합니다(L이 R보다 앞섭니다).
5. 판은 입력에 주어진 방향에서 시작하며, 중력은 아래로 작용합니다. 어떤 회전도 적용하기 전에, 공은 먼저 시작 칸에서 갈 수 있는 만큼 낙하합니다.

회전을 하기 전에 이미 공이 도착점 위에 멈춰 있다면, 순서는 빈 문자열입니다.

첫 번째 줄에 테스트 케이스의 수 $T$ ($1 \le T \le 20$)가 주어집니다. 이어서 각 테스트 케이스가 차례로 주어집니다.

각 테스트 케이스는 미로의 열 수와 행 수를 나타내는 두 정수 nx와 ny가 담긴 줄로 시작합니다. 그다음 ny개의 줄에는 각각 nx개의 문자가 있어 미로의 한 행을 나타냅니다.

• .은 공이 굴러갈 수 있는 빈 칸입니다.
• s는 공의 시작점입니다.
• e는 도착(목표)점입니다.
• 그 밖의 모든 문자는 공이 통과할 수 없는 벽입니다.

각 테스트 케이스마다 한 줄에 Case i: X 형식으로 출력합니다. 여기서 i는 (1부터 시작하는) 테스트 케이스 번호이고, X는 미로를 푸는 회전 순서입니다.

가장 짧은 유효한 순서를 출력하며, 가장 짧은 것이 여러 개이면 사전순으로 가장 앞서는 것을 출력합니다. 미로를 풀 수 없으면 순서 대신 NONE을 출력합니다.