题目描述

WC 没事就上厕所，有一次误入一个迷宫，迷宫中有一些触发式开关，每次经过这些开关时，会把除开关之外的路变成墙，把墙变成路。*表示开关，#表示墙，.表示路 S和T表示起点和终点(起点和终点并不是特殊点，也会随着开关的触发而改变状态)。比如一个图：

3 3
S*.
*..
#.T

走到一个 * 上后，图变为

#*#
*##
.##

那么 WC 到底能不能走出迷宫，如果可以 请输出最短的步数（因为 wc 急着出去学(ce)习(suo)） 如果不能输出 -1。

输入格式

输入一个 $T$ 表示接下来有 $T$ 组数据。

对于每组数据，输入一个 $n,m$ 表示迷宫大小。接下来输入一个 $n\times m$ 的矩阵描述迷宫，其中#表示墙，.表示路，*表示开关，S表示起点，T表示终点。

输出格式

对于每组数据输出一行一个整数表示最短的步数。

样例

输入#1

1
3 3
S*.
*..
#.T

输出#1

6

数据范围

对于 100% 的测试数据满足：$T<50$，$1≤n,m≤100$。