//用算法導(dǎo)論書上最大流做的二分圖匹配，所以內(nèi)存耗的比較大，因?yàn)樾枰?duì)列來存儲(chǔ)增廣路徑
//一個(gè)數(shù)組沒有初始化，wrong了N次
//很多人都是用匈牙利算法做的，偶也準(zhǔn)備學(xué)學(xué)傳說中的匈牙利算法
#include<iostream>
using namespace std;
int h,w,flag,res,node;
int arr[500][500],map[50][20];
int q[10000],pre[10000],used[500];
int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};
int path(int s) //尋找增廣路徑
{ int u,head,tail,temp,i,j;
head=tail=0;
q[tail++]=s;
used[s]=1;
while(head<tail)
{ temp=tail;
for(i=head;i<temp;i++)
{ u=q[i];
if(u==1)
return 1;
for(j=0;j<node;j++)
if(used[j]==0 && arr[u][j]>0)
{pre[j]=u;
used[j]=1;
q[tail++]=j;
}
}
head=temp;
}
return 0;
}
void ford_fulkerson() //修改增光路徑上邊的殘留容量，記錄匹配的結(jié)果
{ int i,j,u,v,min,x,y;
min=INT_MAX;
u=pre[1];
v=1;
while(u>=0)
{if(arr[u][v]<min)
min=arr[u][v];
v=u;
u=pre[u];
}
u=pre[1];
v=1;
while(u>=0)
{ arr[u][v]=arr[u][v]-min;
arr[v][u]=arr[v][u]+min;
v=u;
u=pre[u];
}
res=res+min;
}
int main()
{int i,j,k,Case,x,y;
char c;
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
scanf("%d",&Case);
while(Case--)
{ flag=0;
res=0;
node=2;
scanf("%d%d",&h,&w);
memset(map,0,sizeof(map));
memset(used,0,sizeof(used));
memset(arr,0,sizeof(arr));
for(i=0;i<h;i++)
{getchar();
for(j=0;j<w;j++)
{ scanf("%c",&c);
if(c=='*')
map[i][j]=node++;
}
}
for(i=0;i<h;i++) //構(gòu)圖建模，抽象成二分圖匹配的問題
for(j=0;j<w;j++)
{ if(map[i][j] && !used[map[i][j]])
{ arr[0][map[i][j]]=1;
used[map[i][j]]=1;
for(k=0;k<4;k++)
{ x=i+dx[k];
y=j+dy[k];
if(x>=0 && x<h && y>=0 && y<w && map[x][y])
{arr[map[i][j]][map[x][y]]=1;
arr[map[x][y]][1]=1;
used[map[x][y]]=1;
}
}
}
}
while(!flag)
{ memset(used,0,sizeof(used));
memset(pre,-1,sizeof(pre));
if(path(0))
ford_fulkerson();
else
flag=1;
}
printf("%d\n",node-2-res);
}
return 0;
} 