#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <cmath>
using namespace std;
const int N = 805;

char arr[N][N];
int n, m, cnt, st[N][N];
struct Node{
    int x, y;
}ghost[2], boy, girl;

bool isCaught(int x, int y, int time)
{
    for (int i = 0; i < cnt; ++i)
    {
        if (abs(x-ghost[i].x) + abs(y-ghost[i].y) <= 2 * time) return true;
    }
    return false;
}

bool valid(int x, int y, int time)
{
    return x >= 0 && x < n && y >= 0 && y < m && !isCaught(x, y, time);
}

int bfs()
{
    memset(st, 0, sizeof(st));
    cnt = 0;
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            if (arr[i][j] == 'Z') ghost[cnt++] = {i, j};
            else if (arr[i][j] == 'M') boy = {i, j};
            else if (arr[i][j] == 'G') girl = {i, j};
        }
    }

    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};

    queue<Node> qBoy, qGirl;
    qBoy.push(boy), st[boy.x][boy.y] = 1;
    qGirl.push(girl), st[girl.x][girl.y] = 2;

    int time = 0;
    while (qBoy.size() || qGirl.size())
    {
        ++time;
        for (int i = 0; i < 3; ++i)
        {
            int len = qBoy.size();
            for (int j = 0; j < len; ++j)
            {
                Node cur = qBoy.front();
                qBoy.pop();
                if (isCaught(cur.x, cur.y, time)) continue;
                for (int k = 0; k < 4; ++k)
                {
                    int nx = cur.x + dx[k], ny = cur.y + dy[k];
                    if (valid(nx, ny, time) && arr[nx][ny] != 'X' && st[nx][ny] != 1)
                    {
                        if (st[nx][ny] == 2) return time;
                        st[nx][ny] = 1;
                        qBoy.push({nx, ny});
                    }
                }
            }
        }
        int len = qGirl.size();
        for (int i = 0; i < len; ++i)
        {
            Node cur = qGirl.front();
            qGirl.pop();
            if (isCaught(cur.x, cur.y, time)) continue;
            for (int j = 0; j < 4; ++j)
            {
                int nx = cur.x + dx[j], ny = cur.y + dy[j];
                if (valid(nx, ny, time) && arr[nx][ny] != 'X' && st[nx][ny] != 2)
                {
                    if (st[nx][ny] == 1) return time;
                    st[nx][ny] = 2;
                    qGirl.push({nx, ny});
                }
            }
        }
    }
    return -1;
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d%d", &n, &m);
        for (int i = 0; i < n; ++i) scanf("%s", arr[i]);
        printf("%d\n", bfs());
    }
    return 0;
}