题目描述

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

字符“$\red{.}$”表示道路，字符“$\red{X}$”表示墙，字符“$\red{M}$”表示男孩的位置，字符“$\red{G}$”表示女孩的位置，字符“$\red{Z}$”表示鬼的位置。

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

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

输入格式

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

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

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

输出格式

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

如果无法会合则输出$\red{-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

提示

数据范围：1<n,m<800

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

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