#include <iostream>
#include <cstring>
#include <utility>
#include <queue>
#define PII pair<int,int>
#define p(a,b) make_pair(a,b)
using namespace std;
const int N=801;
const int d[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
struct Node{
    int x,y,ti;
    bool fi;
};
struct Node4{
    int x,y,ti;
    int fi;
};
bool flag=true;
int n,m,gt[N][N],dist[N][N],zt[N][N];
queue<Node> qz;
queue<PII> qg;
queue<Node4> qm;
char map[N][N];
inline void init(){
    memset(zt,127,sizeof(zt));
    memset(gt,255,sizeof(gt));
}
inline void bfs1(int sx,int sy){
    while(qz.size())qz.pop();
    memset(dist,0,sizeof(dist));
    zt[sx][sy]=0,dist[sx][sy]=1;
    qz.push({sx,sy,0,1});
    while(qz.size()){
        Node t=qz.front();
        qz.pop();
        for(int i=0;i<4;i++){
            int nx=t.x+d[i][0],ny=t.y+d[i][1];
            if(nx<1||ny<1||nx>n||ny>m)continue;
            if(!dist[nx][ny]){
                dist[nx][ny]=true;
                zt[nx][ny]=min(zt[nx][ny],t.ti+t.fi);
                qz.push({nx,ny,t.ti+t.fi,!t.fi});
            }
        }
    }    
    return ;
}
inline void bfs2(int sx,int sy){
    if(zt[sx][sy]==1){
        flag=false;
        return ;
    }
    while(qg.size())qg.pop();
    qg.push(p(sx,sy));
    gt[sx][sy]=0;
    while(qg.size()){
        PII t=qg.front();
        // cout<<t.first<<" "<<t.second<<endl;
        qg.pop();
        for(int i=0;i<4;i++){
            int nx=d[i][0]+t.first,ny=d[i][1]+t.second;
            if(nx<1||ny<1||nx>n||ny>m)continue;
            if(gt[nx][ny]==-1&&gt[t.first][t.second]+2<zt[nx][ny]&&map[nx][ny]!='X'){
                // if(nx==7&&ny==6)cout<<gt[t.first][t.second]<<" "<<zt[nx][ny]<<endl;
                gt[nx][ny]=gt[t.first][t.second]+1;
                qg.push(p(nx,ny));
            }
        }
    }
    return ;
}
inline int bfs3(int sx,int sy){
    if(zt[sx][sy]==1)return -1;
    memset(dist,0,sizeof(dist));
    while(qm.size())qm.pop();
    qm.push({sx,sy,0,0});
    dist[sx][sy]=1;
    while(qm.size()){
        Node4 t=qm.front();
        // cout<<t.x<<" "<<t.y<<" "<<t.ti<<endl;
        // cout<<gt[t.x][t.y]<<" "<<zt[t.x][t.y]<<endl;
        // cout<<endl;
        qm.pop();
        if(t.ti>=gt[t.x][t.y]&&t.ti<zt[t.x][t.y]&&gt[t.x][t.y]!=-1){
            // cout<<t.x<<" "<<t.y<<endl;
            return t.ti;
        }
        for(int i=0;i<4;i++){
            int nx=d[i][0]+t.x,ny=d[i][1]+t.y;
            if(nx<1||ny<1||nx>n||ny>m)continue;
            if(!dist[nx][ny]&&t.ti<zt[nx][ny]&&map[nx][ny]!='X'){
                dist[nx][ny]=true;
                qm.push({nx,ny,t.ti+(!(bool)(t.fi%4)),t.fi+1});
            }
        }
    }
    return -1;
}
int main(){
    // freopen("in","r",stdin);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int T;
    cin>>T;
    while(T--){
        int mx,my,gx,gy;
        cin>>n>>m;
        init();
        for(int i=1;i<=n;i++){
            cin>>(map[i]+1);
            for(int j=1;j<=m;j++){
                if(map[i][j]=='Z')
                    bfs1(i,j);
                if(map[i][j]=='M')
                    mx=i,my=j;
                if(map[i][j]=='G')
                    gx=i,gy=j;
            }
        }
        bfs2(gx,gy);
        if(!flag)cout<<"-1\n";
        else cout<<bfs3(mx,my)<<"\n";
    }
    return 0;
}