package SWEA;


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class SWEA_7793_오나의_여신님 {
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder output = new StringBuilder();
	static StringTokenizer tokens;

	static int T;
	static int R, C;
	static char[][] map;
	static Queue<Point> points;
	static int A;

	static int[][] deltas = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };

	public static void main(String[] args) throws IOException {
		input = new BufferedReader(new StringReader(src));
		T = Integer.parseInt(input.readLine());
		for (int t = 1; t <= T; t++) {
			tokens = new StringTokenizer(input.readLine(), " ");
			R = Integer.parseInt(tokens.nextToken());
			C = Integer.parseInt(tokens.nextToken());

			points = new LinkedList<>();
			map = new char[R][];
			Point sPoint = null;
			for (int r = 0; r < R; r++) {
				map[r] = input.readLine().toCharArray();
				for (int c = 0; c < C; c++) {
					if (map[r][c] == '*') {
						points.offer(new Point(r, c, true));
					} else if (map[r][c] == 'S') {
						sPoint = new Point(r, c, false);
					}
				}
			}

//			테케가 들어오고 그 다음줄에 N,M이 들어온다 .
//			큐에 악마들이 다 들어가고 수연이 들어감. 지도 나온 순서대로 넣으면 안됨.

			// 지도 읽기
				// 수연이는 모든 악마가 다 들어간 다음에 동작
			points.offer(sPoint);
			// System.out.println(points);
			A = Integer.MAX_VALUE;
			bfs();
			// 여전히 A가 MAX_VALUE이면 여신을 못만난것.
			output.append("#").append(t).append(" ").append(A==Integer.MAX_VALUE?"GAME OVER":A).append("\n");
		}
		System.out.println(output);
	}

	static void bfs() {
		int turn = 1;
		while (!points.isEmpty()) {
			// 초마다 현재 queue 사용하기...
			int size = points.size();
			while (size-- > 0) {
				Point head = points.poll();

				// 자식 탐색 한다.
				for (int d = 0; d < deltas.length; d++) {
					int nr = head.r + deltas[d][0];
					int nc = head.c + deltas[d][1];

					if (isIn(nr, nc)) {
						// 지금 녀석이 악마라면.. 다음으로 이동은 .과 S
						if (head.isDevil) {
							if (map[nr][nc] == '.' || map[nr][nc] == 'S') {
								map[nr][nc] = '*'; // 방문처리
								points.offer(new Point(nr, nc, true));
							}
						}
						// 지금 녀석이 수연이라면.. . 또는 D (여신 - 만나면 종료)
						else {
							if (map[nr][nc] == 'D') {
								A = turn;
								return;
							} else if (map[nr][nc] == '.') {
								map[nr][nc] = 'S';
								points.offer(new Point(nr, nc, false));
							}
						}
					}
				}
			}
			turn++;
		}
	}

	static boolean isIn(int r, int c) {
		return 0 <= r && r < R && 0 <= c && c < C;
	}

	static class Point {
		int r, c;
		boolean isDevil;

		public Point(int r, int c, boolean isDevil) {
			super();
			this.r = r;
			this.c = c;
			this.isDevil = isDevil;
		}

		@Override
		public String toString() {
			return "[r=" + r + ", c=" + c + ", isDevil=" + isDevil + "]";
		}
	}

	private static String src = "2\r\n" +
			"5 3\r\n" +
			"D*S\r\n" +
			".X.\r\n" +
			".X.\r\n" +
			".X.\r\n" +
			"...\r\n" +
			"5 3\r\n" +
			"D*S\r\n" +
			"...\r\n" +
			".X.\r\n" +
			".X.\r\n" +
			"...";
}