C++ :

/*****************************************
Problem Name  : 
******************************************/
#include <queue>
#include <math.h>
#include <stack>
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
#define LL long long
const int N = 805;
int n , m;
struct node 
{
	int x, y;
}gui[2];
int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};
char dmap[N][N];
int st[N][N];
bool cheak(int x, int y , int time)
{
	if(x < 0 || y < 0 || x >= n || y >= m || dmap[x][y] == 'X')
		return false;
	for(int i = 0 ; i < 2; i++)
	{
		if(abs( x - gui[i].x ) + abs(y - gui[i].y) <= time * 2)
			return false;
	}
	return true;
}
int bfs()
{
	memset(st,0,sizeof(st));
	queue<node> mm , gg;
	int cnt = 0;
	for(int i = 0 ; i < n ; i++)
		for(int j = 0 ; j< m ; j++)
		{
			if(dmap[i][j] == 'M')
			{
				st[i][j] = 2;
				mm.push((node){i,j});
			}
			else if(dmap[i][j] == 'G')
			{
				st[i][j] = 1;
				gg.push((node){i,j});
			}
			else if(dmap[i][j] == 'Z')
				gui[cnt++] = (node){i,j};
		}
	int time = 0;
	node p;
	while(!mm.empty() || !gg.empty())
	{
		time++;
		for(int i = 0 ; i < 3 ; i++)
		{
			for(int j = 0 ,len = mm.size() ; j < len ; j++)
			{
				p = mm.front();
				mm.pop();
				if(cheak(p.x,p.y,time)==false )
					continue;
				for(int k = 0 ; k < 4; k++)
				{
					int x = p.x + dx[k];
					int y = p.y + dy[k];
					if(cheak(x,y,time))
					{
						if(st[x][y] == 1)
							return time;
						if(st[x][y] == 0)
						{
							st[x][y] = 2;
							mm.push((node){x,y});
						}
					}
				}
			}
		}
		for(int i = 0 , len = gg.size() ; i < len ; i++)
		{
			p = gg.front();
			gg.pop();
			if(cheak(p.x,p.y,time)==false )
				continue;
			for(int k = 0 ; k < 4; k++)
			{
				int x = p.x + dx[k];
				int y = p.y + dy[k];
				if(cheak(x,y,time))
				{
					if(st[x][y] == 2)
						return time;
					if(st[x][y] == 0)
					{
						st[x][y] = 1;
						gg.push((node){x,y});
					}
				}
			}
		}
	}
	return -1;

}
int main()
{
	int T;
	cin >> T;
	while(T--)
	{
		cin >> n >> m;
		for(int i = 0 ; i < n ;i++)
			cin >> dmap[i];
		cout << bfs() << endl;
	}
}