화성의 구덩이

로버가 화성 표면을 나타내는 격자 지도 위에서 출발 칸부터 목적지까지 이동해야 한다. 최근 장난꾸러기들이 표면 곳곳에 구덩이를 여러 개 파 놓았고, 로버는 어떤 구덩이에도 빠지면 안 된다. 그래서 목적지에 도달하려면 크게 우회해야 할 수도 있고, 아예 불가능할 수도 있다.

로버는 1초에 명령 하나씩으로 조종한다. 로버는 바라보는 방향과, 초당 칸 수로 나타내는 전진 속도를 가진다. 처음에는 정지해 있고(속도 0) 위쪽을 바라본다. 매 초마다 다음 명령 중 정확히 하나를 내린다.

• 전진(Forward) — 로버가 정지해 있을 때만: 속도 1로 앞으로 굴러가기 시작한다.
• 후진(Backward) — 로버가 정지해 있을 때만: 속도 1로 뒤로 굴러가기 시작한다.
• 가속(Faster) — 로버가 앞으로 움직이는 중일 때만: 전진 속도를 1 늘린다. 최대 5까지 가능하다.
• 감속(Slower) — 로버가 앞으로 움직이는 중일 때만: 전진 속도를 1 줄인다. 0까지 줄일 수 있다.
• 정지(Stop) — 로버의 속도가 즉시 0이 된다.
• 좌회전(Left) / 우회전(Right) — 로버가 정지해 있을 때만: 제자리에서 왼쪽 또는 오른쪽으로 90° 돈다.
• 대기(Wait) — 아무것도 바뀌지 않는다.

전제 조건을 만족하지 못하는 명령(예: 이미 움직이는 중에 내린 전진)은 아무 효과가 없다. 명령을 적용한 뒤, 로버는 그 1초 동안 현재 속도로 나아가 바라보는 방향(후진 중이면 그 반대 방향)으로 속도만큼의 칸을 이동한다. 로버가 지나가는 모든 칸은 물론 그 초가 끝날 때 멈추는 칸까지 전부 빈 칸이어야 하고 지도 안에 있어야 한다. 로버가 구덩이를 가로지르거나 지도 밖으로 나가게 되는 명령은 내릴 수 없다.

지도는 다음 문자로 표현한다. .은 빈 칸, P는 구덩이, R은 로버의 출발 칸, D는 목적지다. R과 D는 각각 정확히 한 번씩 나타난다. 로버는 항상 위쪽을 바라보며 출발한다. 목적지에서 바라보는 방향은 상관없지만, 그곳에서 반드시 정지해 있어야 한다. 로버가 목적지에 도착해 멈추는 데 걸리는 최소 시간(초)을 구하거나, 불가능함을 알려라.

첫 줄에 데이터 집합의 개수 $K$가 주어진다. 이어서 각 데이터 집합이 다음 형식으로 주어진다.

첫 줄에 두 정수 $h$와 $w$가 주어진다($1 \le h, w \le 50$). 각각 지도의 높이와 너비다.

다음 $h$개의 줄에는 각각 $w$개의 문자가 주어지며, 위에서 설명한 문자로 지도의 한 행을 나타낸다.

각 데이터 집합마다 먼저 Data Set x:를 한 줄에 출력한다. 여기서 x는 데이터 집합의 번호다(1부터 시작). 그다음 줄에는 로버가 목적지에 도착해 멈추는 데 걸리는 최소 시간(초)을 출력한다. 목적지에 도달할 수 없으면 대신 Impossible을 출력한다.

연속한 두 데이터 집합 사이에는 빈 줄을 하나 출력한다.