#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,cntt;
char g[805][805];
int gx,gy,bx,by,ex,ey;
int xx[]={0,1,-1,0,0};
int yy[]={0,0,0,1,-1};
int vis[805][805][5],dis[805][805];
int dist(int a,int b,int c,int d){
	return (abs(a-c)+abs(b-d));
}
bool pd(int x,int y,int t,int xb){
	if(x<1||y<1||x>n||y>m||dis[x][y]<=2*(t)||vis[x][y][xb]||g[x][y]=='X')return 0;
	return 1;
}
void bfs(){
#define P pair<int,int>
#define mp(a,b) make_pair(a,b)
	memset(vis,0,sizeof(vis));
	queue<P> bq,gq;
	queue<int> ans1,ans2;
	bq.push(mp(bx,by));vis[bx][by][1]=1;
	gq.push(mp(gx,gy));vis[gx][gy][0]=1;
	ans1.push(0),ans2.push(0);
	while(bq.size()&&gq.size()){
		bx=bq.front().first,by=bq.front().second;
		gx=gq.front().first,gy=gq.front().second;
		int bt=ans1.front(),gt=ans2.front();
		bq.pop(),gq.pop();ans1.pop(),ans2.pop();
		if(dis[bx][by]<=2*(bt+1)||dis[gx][gy]<=2*(gt+1))
			continue;
//		cout<<gt<<" "<<bx<<" "<<by<<" "<<gx<<" "<<gy<<" "<<"\n";
		if(bx==gx&&by==gy){
			cout<<bt<<"\n";
			return;
		}
		queue<P> q1,q2,q3;
		for(int i=1;i<=4;i++){
			int tx=bx+xx[i],ty=by+yy[i];
			if(pd(tx,ty,bt+1,1)){
//				cout<<bt+1<<" "<<(dis[tx][ty]<2*(bt+1))<<" ";
//				cout<<tx<<" "<<ty<<"\n"; 
				vis[tx][ty][1]=bt+1;
				if(tx==gx&&ty==gy){
					cout<<bt+1<<"\n";
					return;
				}
				q1.push(mp(tx,ty));
			}
		}
		while(q1.size()){
			int nbx=q1.front().first,nby=q1.front().second;
			q1.pop();
			for(int i=1;i<=4;i++){
				int tx=nbx+xx[i],ty=nby+yy[i];
				if(pd(tx,ty,bt+1,1)){
					vis[tx][ty][1]=bt+1;
					if(tx==gx&&ty==gy){
						cout<<bt+1<<"\n";
						return;
					}
					q2.push(mp(tx,ty));
				}
			}
		}
		while(q2.size()){
			int nbx=q2.front().first,nby=q2.front().second;
			q2.pop();
			for(int i=1;i<=4;i++){
				int tx=nbx+xx[i],ty=nby+yy[i];
				if(pd(tx,ty,bt+1,1)){
					vis[tx][ty][1]=bt+1;
					if(tx==gx&&ty==gy){
//						cout<<tx<<" "<<ty;
						cout<<bt+1<<"\n";
						return;
					}
					q3.push(mp(tx,ty));
				}
			}
		}
		while(q3.size()){
			int nbx=q3.front().first,nby=q3.front().second;
			bq.push(q3.front());
//			cout<<q3.front().first<<" "<<q3.front().second<<"\n";
			ans1.push(bt+1);
			q3.pop();
		}
		for(int i=1;i<=4;i++){
			int tx=gx+xx[i],ty=gy+yy[i];
			if(pd(tx,ty,gt+1,0)){
				vis[tx][ty][0]=1;
				if(vis[tx][ty][1]==gt+1){
//					cout<<tx<<" "<<ty;
					cout<<gt+1<<"\n";
					return;
				}
				gq.push(mp(tx,ty));
				ans2.push(gt+1);
			}
		}
	}
	cout<<-1<<"\n";
}
signed main(){
//	ios::sync_with_stdio(false);
//	cin.tie(0),cout.tie(0);
	int T;
	cin>>T;
	while(T--){
		cin>>n>>m;
		int gui[3][3]={},zcnt=0;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				cin>>g[i][j];
				if(g[i][j]=='Z'){
					gui[++zcnt][0]=i;
					gui[zcnt][1]=j;
				}
				if(g[i][j]=='M'){
					bx=i,by=j;
				}
				if(g[i][j]=='G'){
					gx=i,gy=j;
				}
			}
		}
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				dis[i][j]=min(dist(i,j,gui[1][0],gui[1][1]),dist(i,j,gui[2][0],gui[2][1]));
			}
		}
		bfs();
	}	
}
/*
1
5 6
XXXXXX
XZ..ZX
XXXXXX
M.G...
......
*/