// Arup Guha
// 7/13/2021
// Solution to 2021 SI@UCF Pages Contest #3 Problem: Fruit Walk

import java.util.*;

public class fruit {

	public static int n;
	public static char[][] grid;
	public static ArrayList<int[]> locs;
	public static int[][] g;

	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++) {
		
			// Read in grid.
			int r = stdin.nextInt();
			int c = stdin.nextInt();
			grid = new char[r][];
			for (int i=0; i<r; i++)
				grid[i] = stdin.next().toCharArray();
			locs = new ArrayList<int[]>();
			
			// Where we start.
			locs.add(new int[]{0,0});
			
			// Store spots.
			n = 0;
			for (int i=0; i<r; i++) {
				for (int j=0; j<c; j++) {
					if (grid[i][j] != '.') {
						n++;
						locs.add(new int[]{i,j});
					}
				}
			}
			
			// Where we end.
			locs.add(new int[]{r-1,c-1});
			g = new int[n+2][n+2];
			
			// Pre-comp these distances.
			for (int i=0; i<n+2; i++)
				for (int j=0; j<n+2; j++)
					g[i][j] = getDist(locs.get(i), locs.get(j));
		
			// Do it!
			System.out.println(go(new int[n], new boolean[n], 0));
		}
	}
	
	// Returns the best answer with the first k items in perm fixed.
	public static int go(int[] perm, boolean[] used, int k) {
		
		// Special case.
		if (n == 0) return g[0][1];
	
		// Normal base case.
		if (k == n) return eval(perm);
		
		// Try each unused item in slot k.
		int res = 1000000;
		for (int i=0; i<n; i++) {
			
			// Skip used items.
			if (used[i]) continue;
			
			// Mark and recurse, updating our result if necessary.
			used[i] = true;
			perm[k] = i;
			res = Math.min(res, go(perm, used, k+1));
			used[i] = false;
		}
		
		// Ta da!
		return res;
	}
	
	// Returns the cost of this permutation.
	public static int eval(int[] perm) {
	
		// Last two legs.
		int res = g[0][perm[0]+1] + g[perm[n-1]+1][n+1];
		
		// Paths between fruit, in order.
		for (int i=0; i<n-1; i++)
			res += g[perm[i]+1][perm[i+1]+1];
			
		// Ta da!
		return res;
	}
	
	// Pre-condition: lengths of a and b are both 2.
	// Returns Manhattan Distance between pts a, b.
	public static int getDist(int[] a, int[] b) {
		return Math.abs(a[0]-b[0]) + Math.abs(a[1]-b[1]);
	}
}