#include<cstdio>

#include<iostream>

#include<queue>

#include<cstring>

#define R register int

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

using namespace std;

inline int g() {

    R ret=,fix=; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-:fix;

    do ret=ret*+(ch^); while(isdigit(ch=getchar())); return ret*fix;

}

int n,m,t,tim,cc;

int gx,gy,mx,my,zx,zy,zx1,zy1;

char e[][];

inline int abs(int x) {return x>?x:-x;}

inline bool is(char ch) {return ch=='X'||ch=='Z'||ch=='M'||ch=='G'||ch=='.';}

inline bool ckpos(int x,int y) {

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

    if(*tim>=abs(x-zx)+abs(y-zy)||*tim>=abs(x-zx1)+abs(y-zy1)) return false;

    return true;

}

struct node{int x,y; node() {}

    node(int xx,int yy) {x=xx,y=yy;}

};

queue<node>q,q1;

inline bool bfs() {

    for(R x=;x<=;++x) { queue<node> qt=q; R sz=q.size();

        while(sz--) {

            node u=qt.front(); qt.pop(); R x=u.x,y=u.y;

            if(!ckpos(x,y)) continue;

            for(R i=;i<;++i) {

                R xx=x+dx[i],yy=y+dy[i];

                if(!ckpos(xx,yy)||e[xx][yy]=='M') continue;

                if(e[xx][yy]=='G') return true; e[xx][yy]='M';

                qt.push(node(xx,yy));

            }

        } q=qt;

    } return false;

}

inline bool bfs1() { queue<node> qt=q1; R sz=q1.size();

    while(sz--) {

        node u=qt.front(); qt.pop(); R x=u.x,y=u.y;

        if(!ckpos(x,y)) continue;

        for(R i=;i<;++i) {

            R xx=x+dx[i],yy=y+dy[i];

            if(!ckpos(xx,yy)||e[xx][yy]=='G') continue;

            if(e[xx][yy]=='M') return true; e[xx][yy]='G';

            qt.push(node(xx,yy));

        }

    } q1=qt; return false;

}

signed main() {

    t=g(); while(t--) { tim=; cc=;

        n=g(),m=g();

        for(R i=;i<=n;++i) for(R j=;j<=m;++j) {

            while(!is(e[i][j]=getchar())); if(e[i][j]=='M') mx=i,my=j;

            else if(e[i][j]=='G') gx=i,gy=j;

            else if(e[i][j]=='Z') if(cc) zx1=i,zy1=j; else zx=i,zy=j,++cc;

        } while(q.size()) q.pop(); while(q1.size()) q1.pop();

        q.push(node(mx,my)); q1.push(node(gx,gy));

        while(++tim) {

            if(bfs()||bfs1()) {printf("%d\n",tim); break;}

            if(q1.empty()||q.empty()) {printf("-1\n"); break;}

        }

    }

}