프로거

필립 J. 프로그(Philip J. Frog)는 한낮에 잠깐 헤엄을 치려 했을 뿐인데, 개구리답게 그만 차들이 붐비는 도로 한복판에 서게 되었습니다. 필립이 시원한 물에 닿기까지 뜨거운 아스팔트 위에서 얼마나 오래 뛰어야 하는지 구해 주세요.

필립은 1초에 상·하·좌·우 중 한 방향으로 한 칸 뛰거나, 제자리에 머무를 수 있습니다. 도로·잔디·물 칸으로만 이동할 수 있고, 나무 칸으로는 갈 수 없으며, 자동차가 있는 칸에는 머무를 수 없습니다.

필립과 자동차는 동시에 움직입니다. 그래서 필립은 마주 오는 자동차를 "뛰어넘을" 수 있습니다(서로 자리를 맞바꾸는 것은 충돌이 아닙니다). 오직 필립이 도착한 칸이 그 순간 자동차가 있는 칸이 아니기만 하면 됩니다.

좌우 이동은 모두 순환합니다. 즉, 가장 오른쪽 열에서 오른쪽으로 뛰면 가장 왼쪽 열로 이동합니다. 위아래 이동은 순환하지 않습니다.

자동차는 지도에 표시된 방향(<는 왼쪽, >는 오른쪽)으로 매초 한 칸씩 좌우로 이동하며 순환하고, 그 무엇과도 충돌하지 않습니다.

입력의 첫 줄에는 지도의 개수를 나타내는 정수 하나가 주어집니다. 각 지도는 행의 수와 열의 수를 나타내는 두 정수 $R$와 $C$ ($0 < R, C \le 30$)로 시작하고, 이어서 각 줄이 $C$개의 문자로 이루어진 $R$개의 줄이 주어져 지도를 나타냅니다. 지도에 쓰이는 문자는 다음과 같습니다.

• 필립(&) — 필립의 시작 칸. 각 지도에 정확히 하나 있으며, 그 아래는 항상 도로입니다.
• 나무(T) — 지나갈 수 없습니다.
• 잔디(.) — 필립이 자유롭게 이동할 수 있습니다.
• 도로(-) — 뜨겁습니다!
• 자동차(<, >) — 그 아래는 항상 도로입니다.
• 물(~) — 필립의 목표입니다.

각 지도에 대해, 필립이 물에 도달하기 위해 도로 칸 위에서 보내야 하는 최소 초를 한 줄에 출력합니다. 필립은 도로 칸(시작 위치)에서 출발하므로 그 1초도 포함됩니다. 물에 도달할 수 있는 이동 방법이 전혀 없으면 대신 Impassable을 출력합니다.