题目描述

给定一张 $N \times M$ 的地图，地图中有 $1$ 个男孩，$1$ 个女孩和 $2$ 个鬼。

字符 . 表示道路，字符 X 表示墙，字符 M 表示男孩的位置，字符 G 表示女孩的位置，字符 Z 表示鬼的位置。

男孩每秒可以移动 $3$ 个单位距离，女孩每秒可以移动 $1$ 个单位距离，男孩和女孩只能朝上下左右四个方向移动。

每个鬼占据的区域每秒可以向四周扩张 $2$ 个单位距离，并且无视墙的阻挡，也就是在第 $k$ 秒后所有与鬼的曼哈顿距离不超过 $2k$ 的位置都会被鬼占领。

注意：每一秒鬼会先扩展，扩展完毕后男孩和女孩才可以移动。

求在不进入鬼的占领区的前提下，男孩和女孩能否会合，若能会合，求出最短会合时间。

输入格式

第一行包含整数 $T$，表示共有 $T$ 组测试用例。

每组测试用例第一行包含两个整数 $N$ 和 $M$，表示地图的尺寸。

接下来 $N$ 行每行 $M$ 个字符，用来描绘整张地图的状况。（注意：地图中一定有且仅有 $1$ 个男孩，$1$ 个女孩和 $2$ 个鬼）

输出格式

每个测试用例输出一个整数 $S$，表示最短会合时间。

如果无法会合则输出 $-1$。

每个结果占一行。

样例

输入样例：

3
5 6
XXXXXX
XZ..ZX
XXXXXX
M.G...
......
5 6
XXXXXX
XZZ..X
XXXXXX
M.....
..G...
10 10
..........
..X.......
..M.X...X.
X.........
.X..X.X.X.
.........X
..XX....X.
X....G...X
...ZX.X...
...Z..X..X

输出样例：

1
1
-1

样例解释

第一个测试用例：地图为：

XXXXXX
XZ..ZX
XXXXXX
M.G...
......

男孩 M 在 (3,0)，女孩 G 在 (3,2)，鬼 Z 在 (1,1) 和 (1,4)。

男孩每秒 3 格，女孩每秒 1 格。
鬼每秒扩张 2 曼哈顿距离。

在 0 秒时，鬼占领距离 ≤0 的点，即鬼自身位置。
男孩和女孩可以在 1 秒后会合，输出 1。

第二个测试用例：类似，可以在 1 秒后会合。

第三个测试用例：地图更大，男孩和女孩无法在鬼扩张前会合，输出 -1。

数据范围

• $1 < N, M < 800$（即 $N, M \ge 2$ 且小于 800）
• $T$ 组测试用例

时空限制

• 时间限制：1 秒
• 空间限制：64 MB