题目描述

把一个机器人放在\(n \times m\)的棋盘中，有些格子上面有障碍，会阻挡机器人通过。初始时机器人位于某一个格子处，面向北方。它可以进行以下三种操作：
（1）原地左转90°；
（2）原地右转90°；
（3）向前方走一格（如果前方一格处没有障碍的话）。
终点位于棋盘的另一个格子。求机器人至少需要几次操作才能到达终点？

格式

输入格式

每个输入文件包含多组测试数据。
文件的第一行是测试数据的组数\(T\)；
每组数据的第一行是两个正整数\(n, m\)，分别表示棋盘的行数和列数，之后以\(n\)行字符串的形式给出棋盘。字符S和T分别代表起点和终点，字符.表示可以走的格子，字符#表示有障碍的格子。输入棋盘时遵循“上北下南，左西右东”的原则。

输出格式

对于每组测试数据，输出一行，包含一个整数：若可以到达终点，则输出最少的操作次数；若不可以，输出-1。

样例

输入

2
5 5
#####
#...#
#.#.#
#S#T#
#####
4 5
#.#.#
#.#.#
#S#T#
#####

输出

8
-1

数据规模及限制

时间限制1s，空间限制128MB
每个输入文件包含\(3 \sim 5\)组测试数据。
\(2 \le n,m \le 300\)

来源

2017.7 太原五中高一集训
From: HDU Online Judge