题目描述

今天的琪露诺依然不想听课，课上她一直在玩赤蛮奇的C程大作业，一款《空洞骑士》的同人游戏"I Wanna Be the Hallownest's Epic Sax Guy"。
这是一款在命令行中操控的2D动作游戏，游戏画面是一个\(R\)行\(C\)列的字符矩阵。每种字符的含义如下：
S和T：分别表示玩家的起点、终点；
.：空格，玩家可以通过；
*：刺，玩家不能到达该位置；
=：砖块，玩家可以站在其正上方，但不可以进入或穿透该位置。
玩家从起点出发，每次可以选择如下三种移动方式之一，一些移动方式会消耗灵魂槽。
（1）向左或向右走一步，不消耗灵魂；
（2）跳跃任意高度，跳到最高点后向左或向右位移一格。若跳跃高度为\(N\)格，则消耗灵魂为\(N^2\);
（3）向左或向右冲刺任意格。若冲刺距离为\(N\)格，则消耗灵魂为\(N^2\)。
移动范围仅限游戏地图之内。
玩家移动到某个位置时，若正下方一格不是平地，则玩家会一直下落，直到落到平地上，或者接触终点或刺，或者掉出游戏地图为止。玩家在下落的过程中不能移动。初始时，起点S的正下方一格一定是平地，即玩家不会在游戏开始时就掉落。玩家在移动过程中接触到终点，则立刻取得胜利；玩家碰到刺或者掉出游戏地图，则玩家死亡，游戏失败。
举例如下：（其中a,b,c是为了便于说明位置而引入的，实际地图中应为.）

.....a.=.
.....=.=.
.......=.
.......=.
...T...=.
b.....S..
=.....==.
.........
.**c**...
...=.....
.........

初始时玩家在S位置。玩家可以通过跳跃到达a位置，跳跃高度为5，因此消耗灵魂为25；玩家也可以冲刺到达b位置，冲刺距离为6，因此消耗灵魂为36。若玩家向右走两格，则会掉出游戏地图。若玩家向左走一格，则会掉落到刺上。
玩家可以通过以下两种方法到达终点：
（1）先向左冲刺3格，掉落到c位置，然后向上跳跃4格。消耗灵魂总量为\(3^2 + 4^2 = 25\)
（2）先向上跳5格到a位置，然后向左冲刺2格，下落过程中接触终点。消耗灵魂\(5^2 + 2^2 = 29\)
琪露诺想请你帮她玩这个游戏，好让她在大妖精面前装X。输入一个游戏地图，请你计算玩家能否到达终点，若能，则求出消耗灵魂的最小值。

输入格式

第一行是一个正整数\(T\)，表示数据组数。
对于每组数据，第一行是两个正整数\(R,C\)，表示地图的行数和列数。之后是\(R\)行字符串，每行\(C\)个字符，从上到下输出游戏地图。保证输入的地图满足如下要求：
（1）不会出现游戏未涉及的字符；
（2）起点的正下方一格一定是平地。

输出格式

每组数据输出一行。如果玩家能到达终点，输出消耗灵魂的最小值；如果不能到达终点则输出-1。

样例

输入

2
7 13
..........S..
..==.*..====.
..=T.=..=....
..=..=.*=....
..=..=..=....
.....=.......
=.==.==.=.=.=
11 9
.......=.
.....=.=.
.......=.
.......=.
...T...=.
......S..
=.....==.
.........
.**.**...
...=.....
.........

输出

42
25

数据规模及约定

\(R \le 120, \quad C \le 120, \quad T \le 5\)
时间限制1s，空间限制64MB。
本题共20组测试文件，部分数据满足如下附加限制：