#include<cstdio>

#include<cstring>

using namespace std;

int n,m,kase=,maxd;

bool vis[][];///表示皇后已经攻击的范围，vis[0][]中存储的是行，vis[1][]中存储的是每列，vis[2][]中存储的是每个副对角线，vis[3][]是每个主对角线

char chess[][];

bool dfs(int pos,int r)

{

    if(pos==maxd){

        for(int i=;i<=n;i++)

        for(int j=;j<=m;j++){

            if(chess[i][j]=='X'&&!vis[][i]&&!vis[][j]&&!vis[][i+j]&&!vis[][i-j+n])///如果达到最大深度，但是仍有X点不处于皇后的攻击范围内，则剪枝

                return false;

        }

        return true;

    }

    for(int i=r;i<=n;i++)///从当前行开始，因为前面的行已经搜索过

    for(int j=;j<=m;j++){

        if(!vis[][i]||!vis[][j]||!vis[][i+j]||!vis[][i-j+n]){///若存在有未被攻击的地方，则进行放棋

            bool v1=vis[][i],v2=vis[][j],v3=vis[][i+j],v4=vis[][i-j+n];

            vis[][i]=vis[][j]=vis[][i+j]=vis[][i-j+n]=true;

            if(dfs(pos+,r+)) return true;///若要放置棋子数最小，则皇后必定会放于是X的位置

            vis[][i]=v1,vis[][j]=v2,vis[][i+j]=v3,vis[][i-j+n]=v4;///还原

        }

    }

    return false;

}

int main()

{

    while(~scanf("%d%d",&n,&m)&&n)

    {

        for(int i=;i<=n;i++) scanf("%s",chess[i]+);

        for(maxd=;maxd<;maxd++)

        {

            memset(vis,,sizeof(vis));

            if(dfs(,)) break;

        }

        printf("Case %d: %d\n",++kase,maxd);

    }

    return ;

}