/*
题意：给你一些冰岛。公共海域和浮冰，冰岛能够隔开两个公共海域，浮冰无影响
求选尽可能多的选一些公共海域点每行每列仅能选一个。
限制条件：冰山能够隔开这个限制条件。即*#*能够选两个
预处理：
*****
**#*#
***** 能够按行转化
*****
**#oo
ooo*#
*****
按行转化的基础上按列转化
***o**o
**ooooo
oooo*oo
**o**o*
由于每行每列顶多能够添加50
所以总共最多2500*2500的矩阵
然后直接二分匹配就可以
*/
#include<stdio.h>
#include<string.h>
#define N 2800
int ma[N][N];
char s[60][60];
int ans[N][N];
int n,m,addx,addy;
void slovex() {//按行转化
int i,k;
addx=0;
for(i=1;i<=n;i++) {
addx++;
//printf("%d
",addx);
k=1;
while(1) {
for(;s[i][k]!='#'&&k<=m;k++) {
if(s[i][k]=='*')
ans[addx][k]=1;
}
if(k==m)//最后一个也要算进去，刚開始这里错了一直没看出来重要*****
ans[addx][k]=2;
if(k==m+1||k==m)
break;
ans[addx][k]=2;
k++;
addx++;
}
}
return ;
}
void slovey() {//在按行转化的基础上按列转化
int i,k;
addy=0;
for(i=1;i<=m;i++) {
addy++;
k=1;
// printf("%d
",addy);
while(1) {
for(;ans[k][i]!=2&&k<=addx;k++) {
if(ans[k][i]==1)
ma[k][addy]=1;
}
if(k==addx+1||k==addx)
break;
k++;
addy++;
}
}
return;
}
int vis[N],link[N];
int findd(int u) {
int i;
for(i=1;i<=addy;i++)
if(ma[u][i]&&vis[i]==0) {
vis[i]=1;
if(link[i]==-1||findd(link[i])) {
link[i]=u;
return 1;
}
}
return 0;
}
int main() {
int t,i,sum,j;
scanf("%d",&t);
while(t--) {
scanf("%d%d",&n,&m);
memset(ma,0,sizeof(ma));
memset(ans,0,sizeof(ans));
for(i=1;i<=n;i++)
scanf("%s",s[i]+1);
slovex();
/* for(i=1;i<=addx;i++) {
for(j=1;j<=m;j++)
printf("%d ",ans[i][j]);
printf("
");
}*/
slovey();
/* for(i=1;i<=addx;i++) {
for(j=1;j<=addy;j++)
printf("%d ",ma[i][j]);
printf("
");
}*/
memset(link,-1,sizeof(link));
sum=0;
for(i=1;i<=addx;i++) {//直接套模板二分匹配就可以
memset(vis,0,sizeof(vis));
sum+=findd(i);
}
printf("%d
",sum);
}
return 0;}