아프슝 피자 배달

아프슝 피자(Afshung-Pizza) 체인은 실다비아(Sildavya)의 한 구역인 하메둥(Hamedung)에서 집집마다 피자를 배달하는 서비스를 운영하고 있으며, 가장 빠른 배달 계획을 세우는 데 여러분의 도움이 필요하다. 모든 배달원은 하메둥의 모든 거리를 보여 주고 고객까지의 경로를 계산해 주는 GIS 장치를 들고 다닌다. 이 장치를 만들고 관리하는 엘야숭(Elyasung) 회사는 장치가 더 빠른 경로를 찾도록 재프로그래밍해 주기를 바란다.

하메둥은 직사각형 모양의 구역이며, 모든 양방향 도로는 축에 나란한(수직·수평) 직선 도로이다. 장치는 다음 기호를 사용해 지도를 문자로 그린다.

• -(대시)는 동서 방향 도로 1km, |(파이프)는 남북 방향 도로 1km를 나타낸다.
• +는 신호등이 없는, 길이가 0인 직각(90도) 회전 지점을 나타낸다.
• 한 자리 숫자 $\tau$(1부터 9까지)는 신호 주기가 $\tau$인 교차로를 나타낸다. 모든 교차로는 삼거리 또는 사거리이다.
• S는 아프슝 피자 지점(출발지), D는 배달지(도착지)를 나타낸다.
• *는 구역의 경계를 나타낸다.

원활하고 사고 없는 교통을 위해, 모든 신호등은 항상 한 방향만 초록불이고 나머지는 빨간불이다(삼거리는 빨간불 2개, 사거리는 빨간불 3개). 한 방향이 $\tau$분 동안, 즉 어떤 $x$에 대해 $[x, x + \tau)$ 동안 초록불을 유지하고, 다음 $\tau$분 동안에는 초록불이 반시계 방향으로 다음 방향으로 옮겨 간다. 이 규칙은 모든 교차로에서 동일하게 적용된다.

배달원이 출발하는 순간을 시각 0으로 둔다. 시각 0에서 모든 교차로는 남쪽 신호등만 초록불이고(남쪽 도로가 없으면 북쪽 신호등이 초록불), 그 교차로의 나머지 신호등은 모두 빨간불이도록 설정된다.

배달원은 회전 지점(+)이나 교차로(숫자)에서만 방향을 바꿀 수 있다. 예를 들어 -|-와 같은 형태에서, 수평으로 이동하는 배달원은 파이프를 가로지를 수도 없고 방향을 바꿀 수도 없다. 그 위치에 교차로가 없기 때문이다.

지도와 지점 S, 도착지 D가 주어질 때, S에서 D까지 피자를 배달하는 가장 빠른 경로를 찾는 프로그램을 작성하라. 다음을 가정한다.

• S와 D는 각각 하나의 - 또는 |를 대체한다.
• S와 D는 어떤 교차로나 회전 지점과도 인접하지 않는다.
• S와 D는 서로 인접하지 않는다.
• 임의의 두 교차로 및/또는 회전 지점은 최소 1km 떨어져 있다.
• S, D, +, 그리고 모든 숫자는 길이가 0이다.
• 배달원의 속도는 분당 1km이다.
• 초록불을 마주한 배달원은 모든 방향(직진, 좌회전, 우회전)으로 이동할 수 있다. 빨간불을 마주한 동안에는 어떤 이동도 할 수 없다.
• 도중에 교통 체증이나 다른 장애물은 없다.

첫째 줄에 테스트 케이스의 수 $t$($1 \le t \le 10$)가 주어진다.

각 테스트 케이스의 첫째 줄에는 지도의 행 수 $N$($1 \le N \le 100$)과 열 수 $M$($2 \le M \le 100$)이 주어진다. 이어지는 $N$개의 줄에는 각각 길이가 $M$인 문자열이 주어지며, 이 문자열은 -, |, +, (공백), *, S, D, 그리고 숫자 1~9로 이루어진다. 교차로와 회전 지점(+)의 총 개수는 최대 100개이다.

각 테스트 케이스마다 한 줄에, S에서 D까지 운전해 가는 최소 시간(분)을 출력한다. D에 도달할 수 없으면 소문자로 impossible을 출력한다.