#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int>> genie;
int hami(int x1, int y1, int x2, int y2) { return abs(x1 - x2) + abs(y1 - y2); }
bool dead(int x, int y, int t)
{
    for (auto i : genie)
    {
        auto [n, m] = i;
        if (t * 2 >= hami(x, y, n, m))
            return 1;
    }
    return 0;
}
char mp[805][805];
short vis[805][805];
int n, m;
queue<pair<pair<int, int>, pair<int, int>>> q;
int d[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
bool BFS_erriyue(int a, int b, int t)
{
    queue<pair<pair<int, int>, int>> qp;
    qp.push({{a, b}, 0});
    vis[a][b] = 1;
    while (qp.size())
    {
        auto val = qp.front();
        int x = val.first.first, y = val.first.second, cnt = val.second;
        qp.pop();
        if (dead(x, y, t + 1))
            continue;
        vis[x][y] = 1;
        for (int i = 0; i < 4; i++)
        {
            int nx = x + d[i][0], ny = y + d[i][1];
            if (nx > n || ny > m || nx < 1 || ny < 1)
                continue;
            if (mp[nx][ny] == 'X')
                continue;

            if (vis[nx][ny] == 1)
                continue;
            if (vis[nx][ny] == 2)
                return 1;
            q.push({{nx, ny}, {t + 1, 1}});
            if (cnt < 3)
                qp.push({{nx, ny}, cnt + 1});
        }
    }
    return 0;
}
void BFS(pair<int, int> st, pair<int, int> en)
{
    vis[st.first][st.second] = 1, vis[en.first][en.second] = 2;
    q.push({{st.first, st.second}, {0, 1}}), q.push({{en.first, en.second}, {0, 2}});
    while (q.size())
    {
        auto [pl, val] = q.front();
        int x = pl.first, y = pl.second, t = val.first, op = val.second;
        q.pop();
        if (t > max(n, m) || dead(x, y, t + 1))
            continue;
        if (op == 1)
        {
            if (BFS_erriyue(x, y, t))
            {
                cout << t + 1 << '\n';
                return;
            }
        }
        else
        {
            vis[x][y] = 2;
            for (int i = 0; i < 4; i++)
            {
                int nx = x + d[i][0], ny = y + d[i][1];
                if (nx > n || ny > m || nx < 1 || ny < 1)
                    continue;
                if (vis[nx][ny] == 2)
                    continue;
                if (mp[nx][ny] == 'X')
                    continue;
                if (vis[nx][ny] == 1)
                {
                    cout << t + 1 << '\n';
                    return;
                }
                q.push({{nx, ny}, {t + 1, 2}});
            }
        }
    }
    cout << "-1\n";
}
void solve()
{
    cin >> n >> m;
    while (q.size())
        q.pop();
    genie.clear();
    pair<int, int> st, en;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            cin >> mp[i][j];
            vis[i][j] = 0;
            if (mp[i][j] == 'Z')
                genie.push_back({i, j});
            if (mp[i][j] == 'M')
                st = {i, j};
            if (mp[i][j] == 'G')
                en = {i, j};
        }
    BFS(st, en);
}
int main()
{
    int T;
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> T;
    while (T--)
        solve();
    return 0;
}

TLE后续再搞,只求会让我WA的数据