/*
  男（三步）女（一步）鬼（上下左右四个方向两个单位）
  鬼会到达两步之内能到达的地方，变为自己的领地

  双向宽搜索，按照秒来搜索，注意可以原地不动
  每一秒宽搜，男孩三步以内能到的位置标记出来
  女孩一步以内能到的位置标记出来，
  如果存在同一秒的是，两个会在同一个位置且当前位置没有鬼
  判断这个位置是否有鬼，可以判断这个位置和鬼的曼哈顿距离是否超过2K
  时间复杂度 O（n）,每个各自只会被遍历一次

 */
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int > PII;
const int N = 810;
int n, m;
char g[N][N];
int st[N][N];
PII ghost[2], boy, girl;

bool check(int x, int y, int step) {
	if (x < 0 || x >= n || y < 0 || y >= m || g[x][y] == 'X' ) return 0;
	for (int i = 0; i < 2; i++) {
		if (abs(x - ghost[i].first) + abs(y - ghost[i].second) <= step * 2)
			return 0;
	}
	return 1;
}


int bfs() {

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

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

	int step = 0;
	queue<PII> qb, qg;
	qb.push(boy), qg.push(girl);
	// 双向 BFS
	while (qb.size() || qg.size()) {
		step++;
		// 男生一次能走三秒
		for (int i = 0; i < 3; i++) {
			for (int j = 0, len = qb.size(); j < len ; j++) {
				auto t = qb.front();
				qb.pop();
				int x = t.first, y = t.second;
				if (!check(x, y, step)) continue;
				for (int k = 0; k < 4 ; k++) {
					int a = x + dx[k], b = y + dy[k];
					if (check(a, b, step)) {
						if (st[a][b] == 2) return step;
						if (!st[a][b]) {
							st[a][b] = 1;
							qb.push({a, b});
						}
					}
				}
			}
		}
		// 女生一次只能走一秒
		for (int i = 0; i < 1; i++) {
			for (int j = 0, len = qg.size(); j < len ; j++) {
				auto t = qg.front();
				qg.pop();
				int x = t.first, y = t.second;
				if (!check(x, y, step)) continue;
				for (int k = 0; k < 4 ; k++) {
					int a = x + dx[k], b = y + dy[k];
					if (check(a, b, step)) {
						if (st[a][b] == 1) return step;
						if (!st[a][b]) {
							st[a][b] = 2;
							qg.push({a, b});
						}
					}
				}
			}
		}
	}
	return -1;
}

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

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e4 + 5;
int n, m, cnt, ans = INT_MAX;
int men[N][4], book[55][55];
char mp[N][N];
bool flag;

struct node {
	int x, y, t;
};

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

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

void bfs() {
	queue<node>q;
	q.push({1, 1, 1}), book[1][1] = 1;
	while (!q.empty()) {
		int nx = q.front().x;
		int ny = q.front().y;
		int nt = q.front().t;
		q.pop();
		if (nx == n and ny == m) {
			cout << nt;
			flag = 1;
			return;
		}
		if (mp[nx][ny] == '$') {
			for (int i = 1; i <= cnt; i++) {
				if (book[men[i][1]][men[i][2]])
					continue;
				book[men[i][1]][men[i][2]] = 1;
				q.push({men[i][1], men[i][2], nt});
			}
		}
		for (int i = 1; i <= 4; i++) {
			int vx = nx + dx[i];
			int vy = ny + dy[i];
			int time = nt + 1;
			if (book[vx][vy] or mp[vx][vy] == '#' or vx < 1 or vy < 1 or vx > n or vy > m)
				continue;
			q.push({vx, vy, time}), book[vx][vy] = 1;
		}
	}
}

signed main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++) {
			cin >> mp[i][j];
			if (mp[i][j] == '$') {
				men[++cnt][1] = i;
				men[cnt][2] = j;
			}
		}
	bfs();
	if (!flag)
		cout << -1;
	return 0;
}

//by.pcx
#include <bits/stdc++.h>
using namespace std;
const int N = 50;
int n, m, vis[N][N][10], flg, sx, sy;
char a[N][N];

int d[4][2] = {0, 1, 0, -1, -1, 0, 1, 0};

struct node {
	int x, y, t, s;
	bool operator < (const node a) const {
		return t > a.t;
	}
};

void bfs() {
	priority_queue<node>q;
	vis[sx][sy][6] = 1;
	q.push({sx, sy, 0, 6});
	while (!q.empty()) {
		node u = q.top();
		q.pop();
		if (u.s <= 0)
			continue;//只是跳过,不能直接return
		if (a[u.x][u.y] == '3' && u.s > 0) {
			cout << u.t;
			flg = 1;
			return;
		}
		for (int i = 0; i < 4; i++) {
			int nx = u.x + d[i][0], ny = u.y + d[i][1];
			if (nx < 1 || nx > n || ny < 1 || ny > m || a[nx][ny] == '0')
				continue;
			int now = u.s - 1;
			if (now <= 0)//要先判断这个，不能先补血
				continue;
			if (a[nx][ny] == '4')
				now = 6;
			if (vis[nx][ny][now])
				continue;
			vis[nx][ny][now] = 1;
			q.push({nx, ny, u.t + 1, now});
		}
	}
	return;
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> a[i][j];
			if (a[i][j] == '2')
				sx = i, sy = j;
		}
	}
	bfs();
	if (!flg)
		cout << "-1";
	return 0;
}

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 10;
int a[N][N], n, m;
int sx, sy, fx, fy;

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

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

struct node {
	int x, y, hp, t;
};
int res = 1e9;
int vis[N][N][7];

void bfs() {
	queue<node> q;
	q.push({sx, sy, 6, 0});
	memset(vis, 0x3f, sizeof(vis));
	vis[sx][sy][6] = 0;

	while (!q.empty()) {
		node t = q.front();
		q.pop();
		if (t.x == fx && t.y == fy) {
			res = min(res, t.t );
		}
		for (int i = 0; i < 4; i++) {
			int nx = t.x + dx[i];
			int ny = t.y + dy[i];
			int hp, cost;
			if (nx < 1 || nx > n || ny < 1 || ny > m)
				continue;
			if (a[nx][ny] == 0)
				continue;
			if (t.hp == 1)
				continue;
			if (a[nx][ny] == 4)
				hp = 6;
			else
				hp = t.hp - 1;
			cost = t.t + 1;
			if (cost < vis[nx][ny][hp]) {
				q.push({nx, ny, hp, cost});
				vis[nx][ny][hp] = cost;
			}
		}

	}
}

signed main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++) {
			cin >> a[i][j];
			if (a[i][j] == 2)
				sx = i, sy = j;
			if (a[i][j] == 3)
				fx = i, fy = j;
		}
	bfs();
	if (res == 1e9)
		cout << -1 << endl;
	else
		cout << res << endl;
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 110;
char a[N][N];
int n, m, sx, sy, fx, fy;

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

int dy[] = {1, -1, 0, 0};
bool vis[N][N], flg = 1;

struct node {
	int x, y, t;
	// 自定义排序规则
	bool operator < (const node a)const {
		return t > a.t;
	}
};

void bfs(int x, int y) {
	vis[x][y] = 1;
	priority_queue<node> q;
	q.push({x, y, 0});
	while (q.size()) {
		auto t = q.top();
		q.pop();
		if (t.x == fx  && t.y == fy) {
			cout << t.t;
			flg = 0;
			return ;
		}
		// 拓展周围的点
		for (int i = 0; i < 4; i++) {
			int nx = t.x + dx[i];
			int ny  = t.y + dy[i];
			if (nx < 1 || nx > n || ny < 1 || ny > m)
				continue;
			if (a[nx][ny] == '#')
				continue;
			if (vis[nx][ny])
				continue;
			vis[nx][ny] = 1;
			if (a[nx][ny] <= '9' && a[nx][ny] >= '1')
				q.push({nx, ny, t.t + 1 + a[nx][ny] - '0'});
			else
				q.push({nx, ny, t.t + 1});
		}
	}
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++) {
			cin >> a[i][j];
			if (a[i][j] == 'Z')
				sx = i, sy = j;
			if (a[i][j] == 'W')
				fx = i, fy = j;
		}
	bfs(sx, sy);
	if (flg)
		puts("IMPOSSIBLE");
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N  = 50;

struct node {
	int x, y, t;
};
int n, m;
char a[N][N];

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

int dy[] = {1, -1, 0, 0};
bool vis[N][N];

void bfs(int x, int y) {
	vis[x][y] = 1;
	queue<node> q;
	q.push({x, y, 1});
	while (q.size()) {
		auto t = q.front();
		q.pop();
		if (t.x == n && t.y == m) {
			cout << t.t;
			return ;
		}
		for (int i = 0; i < 4; i++) {
			int nx = t.x + dx[i];
			int ny = t.y + dy[i];
			if (nx < 1 || nx > n || ny < 1 || ny > m)
				continue;
			if (a[nx][ny] == '#')
				continue;
			if (vis[nx][ny])
				continue;
			vis[nx][ny] = 1;
			q.push({nx, ny, t.t + 1});
		}
	}
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			cin >> a[i][j];
	bfs(1, 1);
	return 0;
}

//queue STL 中的队列

//queue<int> q; // 定义队列
//q.push(x);  // 入队
//q.front(); // 队伍头
//q.pop(); // 出队
//q.size(); // q 的长度
//
//等价于 struct node {
//	int first, second;
//}
//pair<int, int> p;  // 默认的排序规则
//// 先按照 first 从小到大排序，再按照 second 从小到大排序

#include <bits/stdc++.h>
using namespace std;
const int N = 50;
char a[N][N];
int n, m;
bool flg = 1;
bool vis[N][N];
int dx[] = {0, 0, 1, -1};

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

void bfs(int x, int y) {
	queue<pair<int, int> >q;
	vis[x][y] = 1;
	q.push({x, y});
	// 从队列头部开始拓展
	while (q.size()) { // 当队列不为空
		auto t  = q.front();
		q.pop();   // 队列的头
		if (t.first == n && t.second == m) { // 找到了最终的结果
			cout << "YES";
			flg = 0;
			return ;
		}
		// 没有找到，从当前点进行拓展
		for (int i = 0; i < 4; i++) {
			int nx = t.first + dx[i];
			int ny = t.second + dy[i];
			// 越界判断
			if (nx < 1 || nx > n || ny < 1 || ny > m)
				continue;
			// 能否通过
			if (a[nx][ny] == '#')
				continue;
			// 是否走过
			if (vis[nx][ny])
				continue;
			vis[nx][ny] = 1;
			q.push({nx, ny});
		}
	}
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			cin >> a[i][j];
	bfs(1, 1);
	if (flg)
		cout << "NO";
	return 0;
}