一道建图题……

// by SiriusRen

#include <cstdio>

#include <cstring>

using namespace std;

#define N 1666

int h,w,v[N],next[N],first[N],tot,cnt,cases,map[55][55],fa[N],ans;

char a[55][55],xx[]={1,-1,0,0},yy[]={0,0,1,-1},vis[N];

void add(int x,int y){v[tot]=y,next[tot]=first[x],first[x]=tot++;}

bool dfs(int x){

    for(int i=first[x];~i;i=next[i])

        if(!vis[v[i]]){

            vis[v[i]]=1;

            if(!fa[v[i]]||dfs(fa[v[i]]))

                {fa[v[i]]=x;return 1;}

        }

    return 0;

}

int main(){

    scanf("%d",&cases);

    while(cases--){

        tot=0;cnt=ans=0;memset(map,0,sizeof(map));

        memset(first,-1,sizeof(first)),memset(fa,0,sizeof(fa));

        scanf("%d%d",&h,&w);

        for(int i=1;i<=h;i++)

            for(int j=0;j<=w;j++){

                scanf("%c",&a[i][j]);

                if(a[i][j]=='*')map[i][j]=++cnt;

                else map[i][j]=0;

            }

        for(int i=1;i<=h;i++)

            for(int j=1;j<=w;j++)

                if(map[i][j])

                    for(int k=0;k<4;k++)

                        if(map[i+xx[k]][j+yy[k]])

                            add(map[i][j],map[i+xx[k]][j+yy[k]]);

        for(int i=1;i<=cnt;i++,memset(vis,0,sizeof(vis)))

            if(dfs(i))ans++;

        printf("%d\n",cnt-ans/2);

    }

}