import java.util.*;
class Main {
static int N = 810, M = 810;
static char[][] cs = new char[N][M];
static int n, m;
static int[] boy;
static int[] gril;
static Deque<int[]> x;
static boolean[][] st = new boolean[N][M];
static int[][] dir = new int[][]{{1,0}, {-1,0}, {0,1}, {0,-1}};
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while (t-- > 0) {
n = sc.nextInt();
m = sc.nextInt();
sc.nextLine();
x = new ArrayDeque<>();
for (int i = 1; i <= n; i++) {
char[] ss = sc.nextLine().toCharArray();
for (int j = 1; j <= m; j++) {
st[i][j] = false;
cs[i][j] = ss[j - 1];
if (cs[i][j] == 'M') {
boy = new int[]{i, j};
} else if (cs[i][j] == 'G') {
gril = new int[]{i, j};
} else if (cs[i][j] == 'Z') {
st[i][j] = true;
x.addLast(new int[]{i, j});
cs[i][j] = 'X';
}
}
}
int ans = bfs();
System.out.println(ans);
}
}
static Integer hash(int[] loc) {
return loc[0] * m + loc[1];
}
static int bfs() {
Deque<int[]> qa = new ArrayDeque<>(), qb = new ArrayDeque<>();
Map<Integer, Integer> da = new HashMap<>(), db = new HashMap<>();
qa.addLast(boy);
da.put(hash(boy), 0);
qb.addLast(gril);
db.put(hash(gril), 0);
int cnt = 0;
while (!qa.isEmpty() && !qb.isEmpty()) {
int t = 0;
// 鬼:两步
infection();
infection();
// log();
t = move(qa, qb, da, db, cnt++);
if (t != -1) return t;
}
return -1;
}
static int move(Deque<int[]> qa, Deque<int[]> qb, Map<Integer, Integer> da, Map<Integer, Integer> db, int cnt) {
for (int i = 0; i < 3; i++) {
int size = qa.size();
while (size-- > 0) {
int[] poll = qa.pollFirst();
int dx = poll[0], dy = poll[1];
if (cs[dx][dy] == 'X') continue;
for (int[] d : dir) {
int nx = dx + d[0], ny = dy + d[1];
if (nx <= 0 || nx > n || ny <= 0 || ny > m) continue;
if (cs[nx][ny] == 'X') continue;
int[] cur = new int[]{nx, ny};
int key = hash(cur);
if (da.containsKey(key)) continue;
if (db.containsKey(key)) {
// return cnt + 1 + db.get(key);
return cnt + 1;
} else {
qa.addLast(cur);
da.put(key, cnt + 1);
}
}
}
}
for (int i = 0; i < 1; i++) {
int size = qb.size();
while (size-- > 0) {
int[] poll = qb.pollFirst();
int dx = poll[0], dy = poll[1];
if (cs[dx][dy] == 'X') continue;
for (int[] d : dir) {
int nx = dx + d[0], ny = dy + d[1];
if (nx <= 0 || nx > n || ny <= 0 || ny > m) continue;
if (cs[nx][ny] == 'X') continue;
int[] cur = new int[]{nx, ny};
int key = hash(cur);
if (db.containsKey(key)) continue;
if (da.containsKey(key)) {
// return cnt + 1 + da.get(key);
return cnt + 1;
} else {
qb.addLast(cur);
db.put(key, cnt + 1);
}
}
}
}
return -1;
}
static void log() {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
System.out.print(cs[i][j]);
}
System.out.println("");
}
System.out.println("");
}
static void infection() {
int size = x.size();
while (size-- > 0) {
int[] poll = x.pollFirst();
int dx = poll[0], dy = poll[1];
for (int[] d : dir) {
int nx = dx + d[0], ny = dy + d[1];
if (nx <= 0 || nx > n || ny <= 0 || ny > m) continue;
if (!st[nx][ny]) {
cs[nx][ny] = 'X';
st[nx][ny] = true;
x.addLast(new int[]{nx, ny});
}
}
}
}
}