Hypertheseus

An advertising company produces commercials featuring ancient heroes such as Prometheus, Achilles, and Odysseus. To show how hard life was for these heroes, it runs computer simulations of their most famous ordeals. In this problem we simulate the ordeal of Theseus.

Theseus was an Athenian hero who slew the Minotaur, the half-man, half-bull monster that lived in an inescapable Labyrinth. His real challenge was not killing the monster but finding the way out. Here we simulate that task under the following rules.

• The labyrinth is a $d$-dimensional grid of $n_1 \times n_2 \times \cdots \times n_d$ (hyper)cubes. Each cube is either empty (a corridor) or filled with rock (a wall).
• Theseus moves in steps; each step travels between two neighboring empty cubes. Two cubes are neighbors if and only if their coordinates differ by exactly one in a single dimension and are equal in every other dimension.
• Theseus cannot fight the Minotaur bare-handed, so he must first pick up a sword that lies somewhere in the labyrinth. Before he takes the sword, he may not pass through the cube where the Minotaur resides.

The input consists of several labyrinth descriptions. Each description is given as follows.

• The first line contains a single integer $d$ ($2 \le d \le 20$), the number of dimensions.
• The second line contains $d$ space-separated integers $n_1, n_2, \ldots, n_d$, the size of the labyrinth along each dimension in unit cubes, with $n_i \ge 2$ for every $i$. The total number of cubes in any labyrinth does not exceed $2^{20} = 1048576$.
• A labyrinth map follows, described recursively.
  • A two-dimensional labyrinth (of size $n_1 \times n_2$) is given as $n_2$ lines of $n_1$ characters each. Every character describes one cube and is either # (rock), . (free space), or one of the uppercase letters T (Theseus' position), M (Minotaur), and S (sword). Each of T, M, and S appears exactly once in the whole labyrinth, and all three of those cubes count as empty and may be walked through.
  • Each two-dimensional map is followed by one empty line.
  • For $d > 2$, a $d$-dimensional labyrinth is a sequence of $n_d$ "layers", each layer being a description of a $(d-1)$-dimensional labyrinth.

The last labyrinth description is followed by a line containing a single 0, which terminates the input; no output is produced for it.

For each labyrinth, print the line

Theseus needs S steps.

where $S$ is the smallest number of steps needed to start at Theseus' position, reach the cube holding the sword, then reach the cube holding the Minotaur, and finally return to Theseus' original position (where the exit is assumed to be). It is not possible to leave the labyrinth area; every cube outside the labyrinth counts as rock. The exit may lie in an interior cube and need not be on the "border".

If the situation cannot be solved at all, print

No solution. Poor Theseus!