#include <bits/stdc++.h>

using namespace std;

const int N = 8e2 + 5;

char maze[N][N];

int n, m;

bool vis[N][N][2];

int dx[4] = {-1, 1, 0, 0};

int dy[4] = {0, 0, -1, 1};

struct Point	{

	int x, y;

	Point()	{}

	Point(int x, int y)	: x (x), y (y) {}

};

queue<Point> que[2];

Point mm, gg, gho[2];

int get_dis(int x, int y, int ex, int ey)	{

	return abs (ex - x) + abs (ey - y);

}

bool check2(int x, int y, int tim)	{

	for (int i=0; i<2; ++i)	{

		if (get_dis (x, y, gho[i].x, gho[i].y) <= 2 * tim)	return false;

	}

	return true;

}

bool check(int x, int y, int typ)	{

	if (x < 1 || x > n || y < 1 || y > m || maze[x][y] == 'X')	return false;

	else	return true;

}

void init(void)	{

	while (!que[0].empty ())	que[0].pop ();

	while (!que[1].empty ())	que[1].pop ();

	memset (vis, false, sizeof (vis));

}

bool BFS(int typ, int tim)	{

	int sz = que[typ].size ();

	while (sz--)	{

		Point u = que[typ].front ();	que[typ].pop ();

		if (!check (u.x, u.y, typ) || !check2 (u.x, u.y, tim))	continue;

		for (int i=0; i<4; ++i)	{

			int tx = u.x + dx[i], ty = u.y + dy[i];

			if (!check (tx, ty, typ) || !check2 (tx, ty, tim))	continue;

			if (vis[tx][ty][typ^1])	return true;

			if (vis[tx][ty][typ])	continue;

			vis[tx][ty][typ] = true;

			que[typ].push (Point (tx, ty));

		}

	}

	return false;

}

int run(void)	{

	init ();

	vis[mm.x][mm.y][0] = true;

	vis[gg.x][gg.y][1] = true;

	que[0].push (Point (mm.x, mm.y));

	que[1].push (Point (gg.x, gg.y));

	int step = 0;

	while (!que[0].empty () || !que[1].empty ())	{

		++step;

		for (int i=0; i<3; ++i)	{

			if (BFS (0, step))	return step;

		}

		if (BFS (1, step))	return step;

	}

	return -1;

}

int main(void)	{

	int T;	scanf ("%d", &T);

	while (T--)	{

		scanf ("%d%d", &n, &m);

		for (int i=1; i<=n; ++i)	{

			scanf ("%s", maze[i] + 1);

		}

		int t = 0;

		for (int i=1; i<=n; ++i)	{

			for (int j=1; j<=m; ++j)	{

				if (maze[i][j] == 'M')	{

					mm.x = i;	mm.y = j;

				}

				else if (maze[i][j] == 'G')	{

					gg.x = i;	gg.y = j;

				}

				else if (maze[i][j] == 'Z')	{

					gho[t].x = i;	gho[t++].y = j;

				}

			}

		}

		printf ("%d\n", run ());

	}

	return 0;

}