# Appreciation

/*
 * Problem :: 9944 / NxM 보드 완주하기
 *
 * Kind :: DFS + Backtracking
 *
 * Insight
 * - 모든 빈칸에 공을 차레대로 놓아보며
 *   그때 공을 이동시키면서 모든 빈 칸을 방문했는지 알아봐야 할 것 같다
 *   시간상으로는 괜찮을까?
 *   + max(N)=30, max(M)=30
 *     놓을 수 있는 공의 위치 = 900
 *     DFS + Backtracking = ...?
 *     # DFS 한번 돌리는데 900 이라고 치고
 *       그냥 30번 한다고 치면 27000 이니
 *       다 해보면 2.43*10^7 정도여서 괜찮을 것 같다
 *       -> 문제에 보면 가능한 이동 경로의 수는 10^6 을 넘지 않는다니 더욱더 괜찮을 것 같다
 *
 * - 공이 움직이고 난 뒤의 이전상태를 기억해야 한다
 *   + DFS 와 Backtracking 으로 풀자
 *     # 공이 장애물, 보드의 경계, 이미 지나갔던 칸을 만나기 전까지 움직여야 한다는 점을 주의하자
 *       -> while 문을 이용해서 다루어주자
 *
 * Point
 * - 공이 움직일 수 없어서 이동 경로를 확인해야할 때,
 *   보드위의 빈칸이 방문되었는지 안되었는지 확인한다면
 *   O(30^2) 의 시간이 든다
 *   + 그냥 처음부터 방문해야 되는 빈칸의 개수를 모두 세어준뒤
 *     공이 이동할 때마다 그 개수에서 1씩 빼주자
 *     # 확인할 때, 방문해야 되는 빈칸의 개수가 0 이면 유효한 이동 경로이고
 *       그렇지 않으면 유효하지 않은 이동경로임을 쉽게 판별할 수 있다
 */

# Code

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

#include <iostream>

using namespace std;

#define endl '\n'

// Set up : Global Variables
int N, M;
char board[30][30];
bool isVisited[30][30];
int dy[4] = {+1, 0, 0, -1};
int dx[4] = {0, +1, -1, 0};

// Set up : Functions Declaration
bool isValid(int y, int x);
int dfs(int cy, int cx, int cnt, int res);


int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Set up : Input
    int tc = 0; /* 테스트 케이스 번호 */
    while (cin >> N >> M) {
        tc++;
        int res = 0;
        for (int i=0; i<N; i++) {
            for (int j=0; j<M; j++) {
                cin >> board[i][j];
                if (board[i][j] == '.') { res++; } /* 방문해야 되는 빈칸의 개수 */
            }
        }

        // Process
        int ans = -1;
        for (int i=0; i<N; i++) {
            for (int j=0; j<M; j++) {
                if (board[i][j] == '.') { /* 좌표 (i,j) 가 빈칸이면 */
                    isVisited[i][j] = true; /* 공을 놓음 */

                    int temp = dfs(i, j, 0, res-1);
                    if (temp != -1) {
                        if (ans == -1 || ans > temp) {
                            ans = temp;
                        }
                    }

                    isVisited[i][j] = false; /* 공을 뺌 */
                }
            }
        }

        // Control : Output
        printf("Case %d: %d\n", tc, ans);
    }
}

// Helper Functions
bool isValid(int y, int x)
/* 좌표 (y,x) 가 유효하면 true 를 반환, 그 외 false 를 반환 */
{
    return y >= 0 && y < N && x >= 0 && x < M;
}

int dfs(int cy, int cx, int cnt, int res)
/* 현재 상태를 기반으로 현재 좌표로부터 모든 빈칸을 방문하는 최소 이동 횟수를 반환
 * 모든 빈칸을 방문할 수 없으면 -1 을 반환
 * 현재 상태는 다음과 같음
 * 현재 좌표 : (cy,cx)
 * 현재 이동 횟수 : cnt
 * 현재 남은 방문해야되는 빈칸의 개수 : res
 * 현재 방문한 빈칸의 상태 : isVisited 에 저장되어있음 */
{
    /* 움직일 수 있는지 그 여부를 구함 */
    bool canMove = false;
    for (int i=0; i<4; i++) {
        int ay = cy + dy[i];
        int ax = cx + dx[i];
        if (isValid(ay, ax) && board[ay][ax] == '.' && not(isVisited[ay][ax])) {
            canMove = true;
            break;
        }
    }

    /* 움직일 수 없으면 */
    if (not(canMove)) {
        /* 현재 남은 방문해야되는 빈칸의 개수가 0 이면 유효한 이동경로
         * 그렇지 않으면 유효하지 않은 이동경로임 */
        return (res == 0) ? cnt : -1;
    }

    int ret = -1; /* 방문해야되는 최소 이동 횟수 */
    for (int i=0; i<4; i++) {
        int ny = cy + dy[i];
        int nx = cx + dx[i];
        /* 방향 i 로 이동할 수 있으면 */
        if (isValid(ny, nx) && board[ny][nx] == '.' && not(isVisited[ny][nx])) {
            /* 장애물, 보드의 경계, 이미 지나갔던 칸을 만나기 전까지 움직임 */
            while (isValid(ny, nx) && board[ny][nx] == '.' && not(isVisited[ny][nx])) {
                /* 움직일 때마다 현재 상태 갱신 */
                isVisited[ny][nx] = true;
                res--;
                ny += dy[i];
                nx += dx[i];
            }
            /* (ny,nx) 를 갱신한 후에 움직일 수 있는지 확인하므로
             * while 문이 끝났을 때 (ny,nx) 는
             * 실제로 공이 움직인 좌표보다 방향 i 로 한칸 앞에 위치해있음
             * 따라서 뒤로 한칸을 이동 */
            ny -= dy[i];
            nx -= dx[i];

            int temp = dfs(ny, nx, cnt+1, res);
            if (temp != -1) {
                if (ret == -1 || ret > temp) {
                    ret = temp;
                }
            }

            /* 공을 (cy,cx) 로 되돌림 */
            while (ny != cy || nx != cx) {
                isVisited[ny][nx] = false;
                res++;
                ny -= dy[i];
                nx -= dx[i];
            }
        }
    }

    return ret;
}