#include <iostream>#include <cstdlib>#include <cstdio>#include <cstring>using namespace std;const int MAXN = 60;const int MAXM = 3600;struct Edge{ int v, next;}edge[MAXM];char map[MAXN][MAXN];int first[MAXM], link2[MAXM];bool vis[MAXM];int n, m;int cnt;int xn;int xs[MAXN][MAXN], ys[MAXN][MAXN];inline void init(){ cnt = 0; memset(first, -1, sizeof(first)); memset(link2, -1, sizeof(link2)); memset(xs, 0, sizeof(xs)); memset(ys, 0, sizeof(ys));}inline void read_graph(int u, int v){ edge[cnt].v = v; edge[cnt].next = first[u], first[u] = cnt++;}bool ED(int u){ for(int e = first[u]; e != -1; e = edge[e].next) { int v = edge[e].v; if(!vis[v]) { vis[v] = 1; if(link2[v] == -1 || ED(link2[v])) { link2[v] = u; return true; } } } return false;}inline void read_graph2(){ scanf("%d%d", &n, &m); for(int i = 0; i < n; i++) scanf("%s", map[i]); int tot = 0; for(int i = 0; i < n; i++) { int flag = 0; for(int j = 0; j < m; j++) { if(map[i][j] == 'o') { if(flag == 0) tot++; xs[i][j] = tot; flag = 1; } else if(map[i][j] == '#') flag = 0; } } xn = tot; tot = 0; for(int j = 0; j < m; j++) { int flag = 0; for(int i = 0; i < n; i++) { if(map[i][j] == 'o') { if(flag == 0) tot++; ys[i][j] = tot; flag = 1; } else if(map[i][j] == '#') flag = 0; } } for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { int u = xs[i][j], v = ys[i][j]; if(u && v) { read_graph(u, v); } } }}void solve(){ int ans = 0; for(int i = 1; i <= xn; i++) { memset(vis, 0, sizeof(vis)); if(ED(i)) ans++; } printf("%dn", ans);}int main(){ int T, times = 0; scanf("%d", &T); while(T--) { init(); read_graph2(); printf("Case :%dn", ++times); solve(); } return 0;}
