rt

#include <bits/stdc++.h>
#pragma GCC optmize(2)
using namespace std;

#define int long long
int t,n,m;
string s;
int a[805][805];
int sx1,sx2,sy1,sy2,gx[3],gy[3],c;
struct Node{
	int x,y,s;
};
queue<Node> q1,q2;
int dx[5]={0,0,0,1,-1},dy[5]={0,1,-1,0,0};
int tim[805][805][3][30],vis1[805][805],vis2[805][805];

bool die(int x,int y,int t){
	if(abs(gx[1]-x)+abs(gy[1]-y)<=2*t) return 0;
	if(abs(gx[2]-x)+abs(gy[2]-y)<=2*t) return 0;
	return 1;
}

void bfs(){
	memset(tim,0x3f,sizeof(tim));
	memset(vis1,0,sizeof(vis1));
	while(!q1.empty()) q1.pop();
	vis1[sx1][sy1]=1;
	tim[sx1][sy1][1][1]=0;
	q1.push((Node){sx1,sy1,0});
	while(!q1.empty()){
		Node u=q1.front();
		q1.pop();
		for(int i=1;i<=4;i++){
			int sx=u.x+dx[i],sy=u.y+dy[i],ti=(u.s+1)%3?(u.s+1)/3+1:(u.s+1)/3;
			if(sx<1||sx>n||sy<1||sy>m||a[sx][sy]||die(sx,sy,ti)||vis1[sx][sy]) continue;
			q1.push((Node){sx,sy,ti});
			tim[sx][sy][1][++vis1[sx][sy]]=ti;
		}
	}
	memset(vis2,0,sizeof(vis2));
	while(!q2.empty()) q2.pop();
	vis2[sx2][sy2]=1;
	tim[sx2][sy2][2][1]=0;
	q2.push((Node){sx2,sy2,0});
	while(!q2.empty()){
		Node u=q2.front();
		q2.pop();
		for(int i=1;i<=4;i++){
			int sx=u.x+dx[i],sy=u.y+dy[i],ti=u.s+1;
			if(sx<1||sx>n||sy<1||sy>m||a[sx][sy]||die(sx,sy,ti)||vis2[sx][sy]) continue;
			q2.push((Node){sx,sy,ti});
			tim[sx][sy][2][++vis2[sx][sy]]=ti;
		}
	}
	int minn=0x3f3f3f3f;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			for(int l=1,r=1;l<=vis1[i][j]&&r<=vis2[i][j];)
				if((tim[i][j][1][l]==tim[i][j][2][r])||(tim[i][j][1][l]==tim[i][j][2][r]+1)){
					minn=min(minn,tim[i][j][1][l]);
					break;
				}else if(tim[i][j][1][l]>tim[i][j][2][r]) r++;
				else l++;
	cout<<(minn==0x3f3f3f3f?-1:minn)<<endl;
	return;
}

signed main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin>>t;
	while(t--){
		cin>>n>>m;
		c=0;
		for(int i=1;i<=n;i++){
			cin>>s;
			for(int j=0;j<m;j++){
				if(s[j]=='.') a[i][j+1]=0;
				else if(s[j]=='X') a[i][j+1]=1;
				else if(s[j]=='M') sx1=i,sy1=j+1;
				else if(s[j]=='G') sx2=i,sy2=j+1;
				else gx[++c]=i,gy[c]=j+1;
			}
		}
		bfs();
	}
	
	return 0;
}