// Arup Guha
// 7/20/2015
// Solution to 2010 UCF Fall Locals Problem: Knights Exchange

// This is sort of slow, since I build a new board from each mask and go back and forth, but it would have passed in
// the contest, I think. Some clever bitshifting can speed this up a good deal.

import java.util.*;

public class knights {

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

	public static int r;
	public static int c;

	public static void main(String[] args) {

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

		// Process all cases.
		for (int loop=1; loop<=numCases; loop++) {
			r = stdin.nextInt();
			c = stdin.nextInt();
			char[][] grid = new char[r][];
			for (int i=0; i<r; i++)
				grid[i] = stdin.next().toCharArray();

			// Just call bfs and output the result.
			System.out.println("Case #"+loop+": "+bfs(grid)+"\n");
		}
	}

	// Runs a bfs on grid and returns # of moves in fastest solution or -1 if there's no solution.
	public static int bfs(char[][] grid) {

		// Get starting and ending bitmask states for BFS.
		long start = getCode(grid, "X.BW");
		long end = getCode(grid, "X.WB");

		// Set up BFS.
		HashMap<Long,Integer> map = new HashMap<Long,Integer>();
		ArrayDeque<Long> q = new ArrayDeque<Long>();
		q.offer(start);
		map.put(start, 0);

		// Run it.
		while (q.size() > 0) {

			// Grab next board.
			long cur = q.poll();
			int moves = map.get(cur);

			// We made it - return immediately!
			if (cur == end) return moves;

			// Go to all possible next states that are new.
			ArrayList<Long> next = getNext(cur,"X.BW");
			for (Long item: next) {
				if (!map.containsKey(item)) {
					map.put(item, moves+1);
					q.offer(item);
				}
			}
		}

		// Never got to the end state, if we get here.
		return -1;
	}

	// 2 bits per square - code is length 4 and stores encoding.
	public static long getCode(char[][] board, String code) {

		HashMap<Character,Integer> map = getMap(code);

		// Just build the mask, top left is stored in msb.
		long res = 0L;
		for (int i=0; i<r*c; i++)
			res = (res << 2) + map.get(board[i/c][i%c]);
		return res;
	}

	// For easy lookup.
	public static HashMap<Character,Integer> getMap(String code) {
		HashMap<Character,Integer> map = new HashMap<Character,Integer>();
		for (int i=0; i<code.length(); i++)
			map.put(code.charAt(i), i);
		return map;
	}

	public static ArrayList<Long> getNext(long mask, String code) {

		HashMap<Character,Integer> map = getMap(code);
		ArrayList<Long> res = new ArrayList<Long>();

		char[][] board = getBoard(mask, code);

		// Go to each square.
		for (int i=0; i<r; i++) {
			for (int j=0; j<c; j++) {

				// Only try moving valid pieces.
				if (board[i][j] == 'W' || board[i][j] == 'B') {

					// Now try all 8 knight moves.
					for (int k=0; k<DX.length; k++) {
						int x = i+DX[k];
						int y = j+DY[k];
						if (!inbounds(x,y) || board[x][y] != '.') continue;

						// Move it and add appropriate mask.
						swap(board, i, j, x, y);
						res.add(getCode(board, code));

						// Must move back!
						swap(board, i, j, x, y);
					}
				}
			}
		}

		// Here is everything.
		return res;
	}

	// Swaps pieces board[x1][y1] and board[x2][y2].
	public static void swap(char[][] board, int x1, int y1, int x2, int y2) {
		char tmp = board[x1][y1];
		board[x1][y1] = board[x2][y2];
		board[x2][y2] = tmp;
	}

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

	// Returns the board corresponding to mask according to code.
	public static char[][] getBoard(long mask, String code) {
		char[][] res = new char[r][c];
		for (int i=r-1; i>=0; i--) {
			for (int j=c-1; j>=0; j--) {
				res[i][j] = code.charAt((int)(mask & 3));
				mask = mask >> 2;
			}
		}
		return res;
	}
}