题目大意就是有一些'o'和'*'构成的图，每个*可以与其四周的'*'连一条边，但是连完之后这两个‘*’就称作被覆盖了，不能与其他的'*'发生交集了。 然后问用最少的边能把所有的‘*’都覆盖掉
看到是两两连边不由得想起二分图匹配，实际上就是用最少的边覆盖所有的点的问题，我觉得最小边覆盖实际上就是最小路径覆盖的一个特殊情况，只不过要求必须是二分图才行而最小路径覆盖只要是PxP的有向图就行。 而他们的公式都是一样的，都等于最大独立集数
/*
ID: CUGB-wwj
PROG:
LANG: C++
*/
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define INF 100000000
#define MAXN 405
#define PI acos(-1.0)
using namespace std;
char s[55][55];
int mp[55][55];
int xx[] = {0, 0, 1, -1};
int yy[] = {1, -1, 0, 0};
struct node
{int v, next;
}edge[MAXN * MAXN];
int e, head[MAXN], mark[MAXN], cx[MAXN], cy[MAXN], n;
void insert(int x, int y)
{edge[e].v = y;edge[e].next = head[x];head[x] = e++;
}
int path(int u)
{for(int i = head[u]; i != -1; i = edge[i].next){int v = edge[i].v;if(!mark[v]){mark[v] = 1;if(cy[v] == -1 || path(cy[v])){cx[u] = v;cy[v] = u;return 1;}}}return 0;
}
int solve()
{int ans = 0;memset(cx, -1, sizeof(cx));memset(cy, -1, sizeof(cy));for(int i = 1; i <= n; i++){memset(mark, 0, sizeof(mark));ans += path(i);}return ans;
}
int main()
{int T, h, w;scanf("%d", &T);while(T--){e = 0;memset(head, -1, sizeof(head));int cnt = 0;scanf("%d%d", &h, &w);for(int i = 0; i < h; i++) scanf("%s", s[i]);for(int i = 0; i < h; i++)for(int j = 0; j < w; j++)if(s[i][j] == '*') mp[i][j] = ++cnt;for(int i = 0; i < h; i++)for(int j = 0; j < w; j ++){if(s[i][j] != '*') continue;for(int k = 0; k < 4; k++){int tx = i + xx[k];int ty = j + yy[k];if(tx < 0 || ty < 0 || tx >= h || ty >= w || s[tx][ty] != '*') continue;insert(mp[i][j], mp[tx][ty]);}}n = cnt;int ans = n - solve() / 2;printf("%d\n", ans);}return 0;
}