#include <cstdio>

 #include <queue>

 #include <algorithm>

 #include <cmath>

 #include <cctype>

 #include <cstring>

 using namespace std;

 #define res register int

 const int N=+;

 const int dx[]={,-,,},dy[]={,,,-};

 int n,m;

 char s[N][N];

 bool vis[N][N][];

 struct node{

     int x,y;

     node() {};

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

 };

 queue<node> q[];

 node mm,gg,gho[];

 inline int _dis(int a,int b,int x,int y)

 {

     return abs(a-x)+abs(b-y);

 }

 inline bool check(int x,int y) {

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

     else return true;

 }

 inline bool check2(int x,int y,int stp)

 {

     for(res i= ; i<= ; i++)

         if(_dis(x,y,gho[i].x,gho[i].y)<=*stp) return false;

     return true;

 }

 inline bool bfs(int typ,int stp)

 {

     int len=q[typ].size();

     while(len--)

     {

         node u=q[typ].front(); q[typ].pop();

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

         for(res i= ; i< ; i++)

         {

             int nx=u.x+dx[i],ny=u.y+dy[i];

             if(!check(nx,ny) || !check2(nx,ny,stp)) continue;

             if(vis[nx][ny][typ^]) return true;

             if(vis[nx][ny][typ]) continue;

             vis[nx][ny][typ]=;

             q[typ].push(node(nx,ny));

         }

     }

     return false;

 }

 inline void init()

 {

     while(q[].size()) q[].pop();

     while(q[].size()) q[].pop();

     memset(vis,,sizeof(vis));

 }

 inline int run()

 {

     init();

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

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

     q[].push(node(mm.x,mm.y));

     q[].push(node(gg.x,gg.y));

     int stp();

     while(q[].size() || q[].size())

     {

         stp++;

         for(res i= ; i<= ; i++)

             if(bfs(,stp)) return stp;

         if(bfs(,stp)) return stp;

     }

     return -;

 }

 int main()

 {

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

     while(T--)

     {

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

         for(res i= ; i<=n ; i++) scanf("%s",s[i]+);

         int t();

         for(res i= ; i<=n ; i++)

             for(res j= ; j<=m ; j++)

                 if(s[i][j]=='G') {

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

                 }

                 else if(s[i][j]=='M') {

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

                 }

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

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

                 }

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

     }

     return ;

 }