// Arup Guha
// 12/16/2016
// Solution to 2016 Online HS Problem: Overgrown Mazes

import java.util.*;

public class mazes {

	// Directions we can move.
	final public static int[] DX = {-1,0,0,1};
	final public static int[] DY = {0,-1,1,0};

	// Stores the input.
	public static int r;
	public static int c;
	public static char[][] grid;

	public static void main(String[] args) {

		Scanner stdin = new Scanner(System.in);
		int numCases = stdin.nextInt();

		// Process each case.
		for (int loop=1; loop<=numCases; loop++) {

			// Read in the input grid.
			r = stdin.nextInt();
			c = stdin.nextInt();
			grid = new char[r][];
			for (int i=0; i<r; i++)
				grid[i] = stdin.next().toCharArray();

			// Find where to start.
			int start = find('S');

			// Print minimum distance to 'E'.
			System.out.println("Maze #"+loop+": "+bfs(start, 'E'));
		}
	}

	// Returns the first occurrence of ch stored in a single integer.
	public static int find(char ch) {
		int[] res = new int[2];
		for (int i=0; i<r; i++)
			for (int j=0; j<c; j++)
				if (grid[i][j] == ch)
					return c*i+j;
		return -1;
	}

	// Returns the shortest distance (in squares to clear) from location loc to any
	// character endC.
	public static int bfs(int loc, char endC) {

		// Set up our modified BFS.
		PriorityQueue<state> pq = new PriorityQueue();
		boolean[][] used = new boolean[r][c];
		used[loc/c][loc%c] = true;
		pq.offer(new state(loc,0));

		// Go till there are no new places to explore.
		while (pq.size() > 0) {

			// Get next place to build from.
			state cur = pq.poll();
			int curX = cur.loc/c;
			int curY = cur.loc%c;

			// Found it!
			if (grid[curX][curY] == endC) return cur.dist;

			// Try going new places.
			for (int i=0; i<DX.length; i++) {

				// Get next place.
				int nextX = curX + DX[i];
				int nextY = curY + DY[i];

				// Don't go if it's out of bounds or if we've been there before.
				if (!inbounds(nextX, nextY)) continue;
				if (used[nextX][nextY]) continue;

				// Calculate distance to go to this square. (Add 1 if need to cut down corn...)
				int cost = grid[nextX][nextY] == '#' ? cur.dist+1 : cur.dist;

				// Note where we've been and add it to our priority queue.
				used[nextX][nextY] = true;
				pq.offer(new state(nextX*c+nextY, cost));
			}
		}

		// Should never get here for this problem - indicates no solution.
		return -1;
	}

	// Returns true iff (x,y) is within the grid.
	public static boolean inbounds(int x, int y) {
		return x >= 0 && x < r && y >= 0 && y < c;
	}
}

// Needed to use PriorityQueue data struct.
class state implements Comparable<state> {

	public int loc;
	public int dist;


	public state(int location, int distance) {
		loc = location;
		dist = distance;
	}

	public int compareTo(state other) {
		return dist - other.dist;
	}
}