BitmaskDPinGrid

#include<bits/stdc++.h>

using namespace std;

#define ll long long int
#define db(x) cout<<#x<<" -> "<<x<<endl
#define inf (1<<29 )

int mask[12];
int r,c;
ll dp[10][(1<<8)+ 10  ] [(1<<8  )+ 10  ] ;

ll solve (int idx, int previous_mask, int current_mask)
{
    //printf("%d %d %d\n",idx,previous_mask,current_mask);
    if(idx>=r)
    {
        // cout<<"Here"<<endl;
        if( __builtin_popcount(previous_mask)==c  )  return 0LL;
        else     return inf;
    }
//  if(idx>1 &&( previous_mask != ((1<<c)- 1  ) ))
//   {
//  cout<<"Here"<<endl;
//        return inf;
//    }
    if(dp[idx][previous_mask][current_mask]!=-1)
    {
        return dp[idx][previous_mask][current_mask] ;
    }
    ll ret = inf;
    for(int i=0 ;  i <(1<<c  );  i++ )
    {
        int next = mask[idx+1];
        int prev = previous_mask;
        int cur = current_mask;
        int cnt = 0;
        for(int j=0; j<c; j++ )
        {
            if(( i &(1<< j  )) ==0   )
            {
                cnt++;
                cur^=(1<<j );
                next^=(1<<j );
                prev^=(1<<j );
                if(j-1>=0)
                {
                    cur^=(1<<(j-1));
                    next^=(1<<(j-1));
                    prev^=(1<<(j-1));
                }
                if(j+1<c)
                {
                    cur^=(1<<(j+1));
                    next^=(1<<(j+1));
                    prev^=(1<<(j+1));
                }
            }
        }
        if( idx ==0   ||   __builtin_popcount(prev )==c)
        {
            ret = min(ret,cnt+solve(idx+1,cur,next ));
        }
    }
    return dp[idx][previous_mask][current_mask] = ret;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin>>t;
    int tc = 0;
    while(t--)
    {
        cin>>r>>c;
        memset(mask,0,sizeof(mask));
        memset(dp,-1,sizeof(dp));
        for(int i=0; i<r; i++)
        {
            for(int j=0; j<c; j++)
            {
                char ch;
                cin>>ch;
                if(ch=='*')
                {
                    mask[i]|=(1<<j );
                }
            }
        }
        ll ans = solve(0,0,mask[0]);
        if(ans>=inf)
        {
            printf("Case %d: impossible\n",++tc);
            continue;
        }
        printf("Case %d: %lld\n",++tc,ans);
    }
    return 0;
}