时间限制: 3000ms空间限制: 32768K


题目描述


小娜和小冰是两姐妹, 小娜是姐姐, 小冰是妹妹, 一天小冰骑起了它心爱的独轮车, 每个独轮车的轮子有五种颜色, 每种颜色对应的圆心角是度, 如上图, 当我们向前走的时候, 独轮车接触地面的部分颜色变化是蓝->白->绿……构成了一个循环.

爱思考的小娜马上想到:
假如有一个的棋盘, 现在我在点并且朝向北方, 独轮车绿色部分着地, 我能不能到达,忽略独轮车的朝向的情况下仍然是独轮车的绿色部分着地呢?
在棋盘中会有一些障碍物导致独轮车不能到达, 独轮车可以有三种行车模式: 左转, 右转和直走, 并且每一步都会花费等量的时间, 转向不会引起接触点的颜色改变, 直走会使颜色变成下一个颜色, 那么从并且满足条件的最短时间是多少呢? 小娜觉得这个问题太简单了, 但是她想考考你, 你能解出来么?

输入

第一行一个整数代表样例组数
每组样例的第一行有两个整数代表这个棋盘的长和宽.
接下来包括行, 每行个字母其中每个字母:
# 代表障碍物
. 代表空地
S 代表起点
T 代表终点
题目保证只有

输出

每组样例输出占一行: 输出从并且满足条件的最短时间, 如果不能到达输出.

样例输入

2
1 3
S#T
10 10
#S.......#
#..#.##.##
#.##.##.##
.#....##.#
##.##..#.#
#..#.##...
#......##.
..##.##...
#.###...#.
#.....###T

样例输出

-1
49