미노타우로스

문제

크레타 섬에서 발굴 조사를 하던 고고학자 테세우스는 미로의 입구를 발견하고 안으로 들어간다. 미로의 일부를 지도로 그리며 나아가던 그는 어떤 특별한 방에 도착하는데, 그곳에서 그의 숙적 미노스의 영상이 나타난다. 미노스는 테세우스가 이 방을 나서는 순간, 오직 하나의 임무 — 테세우스를 추적하는 것 — 만을 가진 로봇 미노타우로스가 작동한다고 경고한다. 대신 "공정한 승부"를 위해 미노스는 테세우스, 미노타우로스, 그리고 출구의 위치가 표시된 지도를 보여 주며, 미노타우로스가 테세우스보다 두 배 빠르게 움직인다고 알려 준다.

테세우스는 미노타우로스가 이동 방향을 정할 때 사용하는 알고리즘도 함께 보게 된다.

function decideDirection()
    if noWall(myPos.westPos())  and victimPos.isWestOf(myPos)  then return(west)
    if noWall(myPos.eastPos())  and victimPos.isEastOf(myPos)  then return(east)
    if noWall(myPos.northPos()) and victimPos.isNorthOf(myPos) then return(north)
    if noWall(myPos.southPos()) and victimPos.isSouthOf(myPos) then return(south)
    return(none)

탈출 과정을 턴제 게임으로 모형화하자. 미노타우로스가 두 배 빠르므로, 진행 순서는 미노타우로스가 두 번의 턴을 쓰고, 그다음 테세우스가 한 번의 턴을 쓰는 것을 반복한다. 한 번의 턴에 각 캐릭터는 서·동·북·남 중 한 방향으로 한 칸 이동하거나, 그 자리에 그대로 머무를 수 있다.

규칙:

미로는 $w \times h$ 칸의 격자다. 서·동은 가로 방향, 북·남은 세로 방향이며, 지도의 위쪽이 북쪽이다.
미노타우로스는 자신의 각 턴마다 테세우스의 현재 위치를 기준으로 decideDirection을 실행한다(미노타우로스가 두 턴을 쓰는 동안 테세우스는 움직이지 않는다). 그리고 정해진 방향으로 한 칸 이동하며, 결과가 none이면 제자리에 머문다. noWall(p)는 칸 p가 미로 안에 있고 벽이 아닐 때 참이다. isWestOf 등은 두 위치를 한 축을 따라 비교한다.
미노타우로스가 테세우스와 같은 칸에 놓이는 순간, 테세우스는 붙잡힌다.
테세우스가 출구 칸에 들어서는 순간, 그는 탈출한다.

테세우스가 탈출하는 데 필요한 최소 턴 수를 구하라.

입력

첫 줄에는 테스트 케이스의 수가 주어진다. 각 테스트 케이스의 형식은 다음과 같다.

두 정수 $w$와 $h$가 주어지는 한 줄 ($1 \le w \le 50$, $1 \le h \le 50$). $w$는 미로의 동서 방향 너비, $h$는 남북 방향 높이를 칸 수로 나타낸다.
정확히 $w$개의 문자로 이루어진 $h$개의 줄. 가장 북쪽 줄부터 가장 남쪽 줄까지, 각 줄 안에서는 가장 서쪽부터 가장 동쪽 순서로 미로를 나타낸다. 각 문자의 의미는 다음과 같다.
- # — 벽 칸
- . — 빈 칸
- T — 테세우스의 시작 칸
- M — 미노타우로스의 시작 칸
- X — 출구

각 테스트 케이스에서 T, M, X는 각각 정확히 한 번씩 나타난다. 미로 전체는 벽으로 둘러싸여 있지만, 그 벽은 입력에 포함되지 않는다. 출구는 지붕에 뚫린 구멍이므로 미로 어디에나 있을 수 있다. 테세우스에서 출구까지 벽이 아닌 칸으로 이어지는 경로가 반드시 존재함이 보장된다.

출력

각 테스트 케이스마다 한 줄에 정수 하나를 출력한다. 테세우스가 탈출하는 데 필요한 최소 턴 수이며, 미노타우로스의 턴은 세지 않고 오직 테세우스 자신의 턴만 센다. 테세우스가 결코 안전하게 출구에 도달할 수 없다면 0을 출력한다.