// Arup Guha
// 2/26/2024
// Solution to COP 4516 Individual Final Contest Problem D: Island of Valcu

import java.util.*;

public class valcu {

	final public static int[] DX = {-1,0,0,1};
	final public static int[] DY = {0,-1,1,0};

	public static int r;
	public static int c;
	public static char[][] g;
	public static int sV;
	public static int eV;
	public static int[] dist;
	
	public static void main(String[] args) {
	
		Scanner stdin = new Scanner(System.in);
		int nC = stdin.nextInt();
		
		// Process cases.
		for (int loop=0; loop<nC; loop++) {
			r = stdin.nextInt();
			c = stdin.nextInt();
			g = new char[r][];
			
			// Read grid figure out start and end.
			sV = -1;
			eV = -1;
			for (int i=0; i<r; i++) {
				g[i] = stdin.next().toCharArray();
				for (int j=0; j<c; j++) {
					if (g[i][j] == 'S') sV = c*i+j;
					if (g[i][j] == 'E') eV = c*i+j;
				}
			}
			
			// Find distances of each square from a volcano, return in reverse
			// sorted order.
			ArrayDeque<Integer> locs = volcanobfs();
			
			// Make a disjoint set.
			djset dj = new djset(r*c);
			
			// Will get overwritten.
			int res = -1;
			
			/*** The idea is as follows, we will start fusing together 
			squares that are farther from volcanos together into the
			same connected component. When S and E are in the same
			connected component, that means there must be some path
			from S to E that only uses the squares we fused. The distance
			the last fused square is from some volcano is our answer. ***/
			
			// Go in order. From farthest point from volcano to closest.
			while (locs.size() > 0) {
			
				// Extract this point.
				int code = locs.pollFirst();
				int x = code/c;
				int y = code%c;
				
				// Look at its neighbors.
				for (int i=0; i<DX.length; i++) {
					int nX = x + DX[i];
					int nY = y + DY[i];
					if (!inbounds(nX, nY)) continue;
					
					// Fuse them if both are at least this distance away.
					if (dist[nX*c+nY] >= dist[code])
						dj.union(code, nX*c+nY);
				}
				
				// These two are now connected, so this is my answer.
				if (dj.find(sV) == dj.find(eV)) {
					res = dist[c*x+y];
					break;
				}
			
			}
			
			// Ta da!
			System.out.println(res);
		}
	}
	
	// Returns a list in reverse order of distance from the volcanos.
	public static ArrayDeque<Integer> volcanobfs() {
	
		ArrayDeque<Integer> res = new ArrayDeque<Integer>();
		dist = new int[r*c];
		Arrays.fill(dist, -1);
		
		// Add each volcano to bfs queue.
		ArrayDeque<Integer> q = new ArrayDeque<Integer>();
		for (int i=0; i<r*c; i++) {
			if (g[i/c][i%c] == '*') { 
				q.offer(i);
				dist[i] = 0;
			}
		}
		
		// Run a regular BFS.
		while (q.size() > 0) {
		
			// Get the next item from the queue.
			int cur = q.poll();
			int cX = cur/c, cY = cur%c;
			
			// Look at all neighboring squres.
			for (int i=0; i<DX.length; i++) {
				int nX = cX + DX[i];
				int nY = cY + DY[i];
				if (!inbounds(nX, nY) || dist[nX*c+nY] != -1) continue;
				
				// If we get here, lava can get here in 1 more day, so mark
				// distance and add to queue.
				dist[nX*c+nY] = dist[cur] + 1;
				res.addFirst(nX*c+nY);
				q.offer(nX*c+nY);
			}
		}
				
		return res;
	}
	
	public static boolean inbounds(int x, int y) {
		return x>=0 && x<r && y>=0 && y<c;
	}
}



class djset {

	public int[] par;
	
	public djset(int n) {
		par = new int[n];
		for (int i=0; i<n; i++)
			par[i] = i;
	}
	
	public int find(int u) {
		if (par[u] == u) return u;
		return par[u] = find(par[u]);
	}
	
	public boolean union(int u, int v) {
		u = find(u);
		v = find(v);
		if (u == v) return false;
		par[v] = u;
		return true;
	}
}