蜂巢是由蜜蜂建造的蜡质蜂房，可以描述为欧几里得平面上的正六边形平铺，其中每个内部顶点都有三个六边形相交。六边形的内角为 $120$ 度，因此在一点处三个六边形构成完整的 $360$ 度。下图展示了一个 $3$ 行 $4$ 列的完整蜂巢。

我们保证第二列的第一个单元格总是位于第一列第一个单元格的右下方，如上图所示。一般的蜂巢可以在完整蜂巢的基础上，去掉相邻单元格之间的一些壁，但蜂巢仍然保持封闭形式。一种可能的情况如下图所示。

Hamilton 是一只生活在一般蜂巢中的勇敢蜜蜂。现在他想从起点移动到指定的终点。下图给出了一个 $3 \times 4$ 蜂巢中从第 $2$ 列第 $1$ 个单元格到第 $4$ 列第 $1$ 个单元格的可行路径。

请帮助他找到从指定起点到终点，一条可行路径所必须经过的最少单元格数量（包括起点和终点）。

输入格式

输入包含多个测试用例，第一行包含一个正整数 $T$，表示测试用例的数量，最多为 $10^4$。

对于每个测试用例，第一行包含两个整数 $r$ 和 $c$，表示蜂巢的行数和列数，其中 $2 \le r, c \le 10^3$。

接下来的 $(4r+3)$ 行描述了整个给定的蜂巢，每行最多包含 $(6c+3)$ 个字符。奇数行包含用加号（“+”）表示的网格顶点和零个或多个水平边，而偶数行包含两个或多个对角边。具体来说，一个单元格由 $6$ 个顶点和最多 $6$ 条边描述。其上边界或下边界由三个连续的减号（“-”）表示。它的每一条对角边（如果存在）是一个正斜杠（“/”）或反斜杠（“\”）字符。所有边字符都将精确放置在相应的顶点之间。在起始单元格（或终点）的中心，使用大写字母“S”（或大写字母“T”）作为特殊字符来指示该特殊单元格。所有其他字符均为空格。注意，如果任何输入行包含尾随空格，该空格将被忽略。

我们保证所有最外层的墙都存在，使得给定的蜂巢是封闭的，并且在给定的蜂巢中恰好出现一个“S”和一个“T”。此外，所有测试用例中 $r \cdot c$ 的总和最多为 $2 \times 10^6$。

输出格式

对于每个测试用例，输出一行，包含 Hamilton 从起始单元格（“S”）移动到终点（“T”）所必须访问的最少单元格数量，包括起始单元格和终点。如果不存在可行路径，则输出 $-1$。

样例

输入 1

1
3 4
+---+ +---+
/ \ / \
+ +---+ +---+
\ \ / \
+ + S +---+ T +
/ \ / /
+ +---+ + +
\ \ / \
+---+ +---+ +
/ /
+ +---+ + +
\ / \
+---+ +---+ +
\ / \ /
+---+ +---+

输出 1

7