Racing

For his birthday, young technician Misha received a radio-controlled car. Misha quickly grew bored of driving the car back and forth around the room, so he built a special track. He divided the room into square cells, left some of them empty, and placed obstacles in others. For a whole week, Misha improved his record for completing the track every day. But how disappointed he was when his friend Tima came to visit with his own car and beat his record. It became clear that the car had to be upgraded.

During test runs made a day later, Misha discovered that the car did indeed drive better, but its behavior had changed somewhat. Now only four buttons on the remote work: forward, backward, right, left. When one of them is pressed, the car drives toward the corresponding wall of the room, which is also the boundary of the track, exactly perpendicular to that wall. The car accelerates so much that it stops responding to other commands, crashes into the nearest obstacle or wall, and bounces off it by half the distance it traveled. That is, if there were $x$ empty cells between the car and the wall, then after the bounce it stops on the cell that is $\left\lfloor\frac{x}{2}\right\rfloor$ cells from the wall ($\lfloor x\rfloor$ denotes rounding down; for example, $\left\lfloor\frac{4}{2}\right\rfloor=2$, $\left\lfloor\frac{5}{2}\right\rfloor=2$).

Now Misha wonders what the minimum number of times the remote buttons must be pressed for the car, starting in the start cell, to stop in the finish cell.

The first line of the input file contains two integers $n$ and $m$, the dimensions of the track ($2 \le m, n \le 20$). The next $n$ lines contain $m$ characters each: the character <<.>> corresponds to an empty cell, <<\#>> to an obstacle, and <<S>> and <<T>> to the start cell and the finish cell, respectively.

Print the minimum number of button presses on the remote needed to drive the car along the track from the start to the finish.

If it is impossible to get from the start to the finish, print $-1$.