Minotaur

While excavating on the island of Crete, the archaeologist Theseus discovers the entrance to a maze and steps inside. After mapping part of it, he reaches a special hall, where a projection of his rival Minos appears. Minos warns that the moment Theseus leaves the hall, a robot called the Minotaur is activated with one single mission: hunt Theseus down. To make it a "fair" game, Minos reveals a map showing the positions of Theseus, the Minotaur, and the exit, and tells Theseus that the Minotaur moves twice as fast as he does.

Theseus also sees the algorithm the Minotaur uses to choose its direction:

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)

Model the escape as a turn-based game. Because the Minotaur is twice as fast, play repeats in the order the Minotaur takes two turns, then Theseus takes one turn. On a single turn a character may move one square west, east, north, or south, or stay where it is.

Rules:

• The maze is a grid of $w \times h$ squares. West and east are the horizontal directions, north and south the vertical ones; north is the top of the map.
• On each of its turns the Minotaur runs decideDirection using Theseus's current position (Theseus does not move while the Minotaur takes its two turns), then moves one square in the chosen direction, or stays put if the result is none. noWall(p) is true when square p lies inside the maze and is not a wall; isWestOf and the others compare the two positions along a single axis.
• The Minotaur catches Theseus the instant they occupy the same square.
• Theseus escapes the instant he steps onto the exit square.

Compute the fewest turns Theseus needs to escape.

The first line contains the number of test cases. Each test case has the following format:

• One line with two integers $w$ and $h$ ($1 \le w \le 50$, $1 \le h \le 50$): the width (east-west) and height (north-south) of the maze, measured in squares.
• $h$ lines of exactly $w$ characters each, describing the maze from the northernmost row to the southernmost, and within each row from west to east. The characters mean:
  • # — a wall square
  • . — an empty square
  • T — Theseus's starting square
  • M — the Minotaur's starting square
  • X — the exit

Each of T, M, and X appears exactly once in every test case. A wall surrounds the entire maze but is not part of the input. The exit is an opening in the roof, so it may be anywhere in the maze. It is guaranteed that a path of non-wall squares exists from Theseus to the exit.

For each test case, print a single line containing one integer: the minimum number of turns Theseus needs to escape, counting only Theseus's own turns and not the Minotaur's. Print 0 if Theseus can never reach the exit safely.