자동차 경주

어린 기술자 미샤는 생일 선물로 무선 조종 자동차를 받았다. 미샤는 방 안에서 자동차를 이리저리 몰고 다니는 것이 금세 지겨워져서 특별한 트랙을 만들었다. 방을 정사각형 칸으로 나누고, 일부 칸은 비워 두었으며 일부 칸에는 장애물을 놓았다. 미샤는 일주일 동안 매일 트랙을 통과하는 자신의 기록을 갱신했다. 그런데 친구 티마가 자기 자동차를 가지고 놀러 와서 미샤의 기록을 깨뜨렸다. 자동차를 개조해야 한다는 것이 분명해졌다.

하루 뒤에 진행한 시험 운전에서 미샤는 자동차가 확실히 더 잘 달리기는 하지만 움직임이 다소 달라졌다는 것을 알아냈다. 이제 조종기에는 앞으로, 뒤로, 오른쪽, 왼쪽 네 개의 버튼만 작동한다. 버튼을 누르면 자동차는 트랙의 경계이기도 한 방의 해당 벽을 향해 그 벽에 정확히 수직으로 달린다. 자동차는 다른 명령에 반응하지 않을 만큼 속력을 내고, 가장 가까운 장애물이나 벽에 부딪혀 지나온 거리의 절반만큼 튕겨 나온다. 즉 자동차와 벽 사이에 빈 칸이 $x$개 있었다면 튕겨 나온 뒤에는 벽에서 $\left\lfloor\frac{x}{2}\right\rfloor$칸 떨어진 칸에 멈춘다($\lfloor x\rfloor$는 내림을 뜻하며, 예를 들어 $\left\lfloor\frac{4}{2}\right\rfloor=2$, $\left\lfloor\frac{5}{2}\right\rfloor=2$이다).

이제 미샤는 자동차가 출발 칸에서 시작해 도착 칸에 멈추려면 조종기의 버튼을 최소 몇 번 눌러야 하는지 궁금하다.

첫째 줄에 트랙의 크기 $n$과 $m$이 주어진다($2 \le m, n \le 20$). 다음 $n$개 줄에는 각각 $m$개의 문자가 주어진다. 문자 <<.>>는 빈 칸, <<\#>>는 장애물, <<S>>와 <<T>>는 각각 출발 칸과 도착 칸이다.

자동차를 트랙에서 출발 칸부터 도착 칸까지 이동시키기 위해 조종기의 버튼을 눌러야 하는 최소 횟수를 출력한다.

출발 칸에서 도착 칸으로 갈 수 없다면 $-1$을 출력한다.