暂无测试数据。

前面的迷宫都是静态的，今天蒜头君打算测试一下动态迷宫。迷宫中有一些动态楼梯，它们每隔一分钟就变动一次方向。

比如下面的例子里，一开始楼梯在竖直方向，一分钟以后它移动到了水平方向，再过一分钟它又回到了竖直方向。蒜头君发现对他来说很难找到能使得他最快到达目的地的路线，这时聪明的蒜头君便想到了万能的你，来解决这个问题。

已知蒜头君每次只能移动到与他相邻的四个格子中，并且每次移动的时间是一分钟。若蒜头君遇到楼梯：

• 如果蒜头君的前进方向与当前楼梯的方向一致（同时为水平或竖直），则通过楼梯不需要花费时间。
• 如果蒜头君的前进方向与当前楼梯的方向不一致，则可以停留在原地。

输入格式

第一行有两个数 $M$ 和 $N$。

接下来是一个 $M$ 行 $N$ 列的地图，'*'表示障碍物，'.'表示走廊，'|'或者'-'表示一个楼梯，并且标明了它在一开始时所处的位置:'|'表示的楼梯在最开始是竖直方向，'-'表示的楼梯在一开始是水平方向。地图中还有一个'S'是蒜头君的位置，'T'是目标，$0 \le M,N \le 20$，地图中不会出现两个相连的楼梯。蒜头君每秒只能停留在'.'或'S'和'T'所标记的格子内。

输出格式

输出一个整数，表示到达目标的最短时间。

注意：蒜头君只能每次走到相邻的格子而不能斜走，每移动一次恰好为一分钟，并且蒜头君登上楼梯并经过楼梯到达对面的整个过程只需要一分钟，蒜头君从来不在楼梯上停留。并且每次楼梯都恰好在蒜头君移动完毕以后才改变方向。

数据范围

$1 \le N,M \le 10$。

5 5
**..T
**.*.
..|..
.*.*.
S....

7

5 5
**..T
**.*.
.*|..
.*.*.
S...*

8