/**
题目：poj3020 Antenna Placement
链接：http://poj.org/problem?id=3020
题意：
给一个由'*'或者'o'组成的n*m大小的图，你可以用一个小圈圈圈住两个相邻的'*'，问要圈住所有的'*'最少需要多少个小圈圈。（小圈圈可以相交） 思路：
先尽量圈出能圈两个且不重复圈的'*'。剩下的没有圈的'*'一定需要用一个。
所以构造二分图，求最大匹配，结果：ans = 总的'*'数量-最大匹配数*2 + 最大匹配数 = 总的'*'数量-最大匹配数； 用自身对应自身构造的二分图，求得的最大匹配数要对半才是上面要求的最大匹配数。 */ #include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<vector>
#include<queue>
#include<set>
#include<cstring>
using namespace std;
const int MAXN = ;///n*m=400
int f[MAXN][MAXN];
int vit[MAXN], S[MAXN], T[MAXN];
int N;
///模板
bool Find(int x)///走交替路，寻找增广路
{
for(int i = ; i <= N; i++){///n表示右侧点数。
if(f[x][i]&&vit[i]==){
vit[i] = ;
if(T[i]==||Find(T[i])){
T[i] = x;///右边第i个点和左边第x个点匹配成功。
S[x] = i;///左边第x个点和右边第i个点匹配成功。
return true;
}
}
}
return false;
}
char str[][];
int main()
{
int n, m, k;
cin>>k;
while(k--){
scanf("%d%d",&n,&m);
N = n*m;
for(int i = ; i <= n; i++){
scanf("%s",str[i]+);
}
memset(f, , sizeof f);
memset(S, , sizeof S);
memset(T, , sizeof T);
int cnt = ;///'*'的个数
for(int i = ; i <= n; i++){
for(int j = ; j <= m; j++){
if(str[i][j]=='*'){
cnt++;
if(j+<=m&&str[i][j+]=='*'){///向右边，和下边找，以免重复。
f[(i-)*m+j+][(i-)*m+j] = f[(i-)*m+j][(i-)*m+j+] = ;///两边都是相同的数据，所以最大匹配数结果是两倍。
///最终要除以2。
}
if(i+<=n&&str[i+][j]=='*'){
f[i*m+j][(i-)*m+j] = f[(i-)*m+j][i*m+j] = ;
}
}
}
}
int ans = ;
for(int i = ; i <= N; i++){
memset(vit, , sizeof vit);
if(Find(i)) ans++;
}
printf("%d\n",cnt-*(ans/)+(ans/));/// cnt - ans/2;
}
return ;
}