/*
  Solucao do problema No Cheating
  Complexidade: O(C(NM)^2)
*/

#include <bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;
const int MAXN = 100;

struct Graph {
    struct Edge {
        int v, u;
        Edge(int _v, int _u) : v(_v), u(_u) {}
    };

    int n;
    vector<Edge> edges;
    vector<vector<int>> adj;

    Graph(int _n) : n(_n) { adj.resize(n); }

    void add_edge(int v, int w, int u) {
        adj[v].push_back(edges.size());
        edges.push_back(Edge(w, u));
        adj[w].push_back(edges.size());
        edges.push_back(Edge(v, 0));
    }
};

int augment(Graph &g, int s, int t) {
    vector<int> prv(g.n, -1), flow(g.n);
    prv[s] = s;
    flow[s] = INF;
    queue<int> queue({s});
    while (!queue.empty() && prv[t] == -1) {
        int v = queue.front();
        queue.pop();
        for (int i: g.adj[v]) {
            int w = g.edges[i].v, u = g.edges[i].u;
            if (prv[w] == -1 && u > 0) {
                prv[w] = i;
                flow[w] = min(flow[v], u);
                queue.push(w);
            }
        }
    }
    if (prv[t] == -1) return 0;
    for (int v = t; v != s; v = g.edges[prv[v] ^ 1].v) {
        g.edges[prv[v]].u -= flow[t];
        g.edges[prv[v] ^ 1].u += flow[t];
    }
    return flow[t];
}

int maxflow(Graph &g, int s, int t) {
    int total_flow = 0, cur_flow;
    do {
        cur_flow = augment(g, s, t);
        total_flow += cur_flow;
    } while (cur_flow > 0);
    return total_flow;
}

char grid[MAXN][MAXN];

int main() {
    int C, cur_case = 1;
    for (scanf("%d", &C); C--;) {
        int N, M;
        scanf("%d%d", &N, &M);
        Graph g(N * M + 2);
        int s = N * M, t = N * M + 1;
        int V = 0;
        for (int r = 0; r < N; r++) {
            for (int c = 0; c < M; c++) {
                scanf(" %c", &grid[r][c]);
                if (grid[r][c] == '.') {
                    if (c % 2 == 0) g.add_edge(s, r * M + c, 1);
                    else g.add_edge(r * M + c, t, 1);
                    V++;
                }
            }
        }

        for (int c = 0; c < M; c += 2) {
            for (int r = 0; r < N; r++) {
                if (grid[r][c] != '.') continue;
                for (int dc = -1; dc <= 1; dc += 2) {
                    if (c + dc < 0 || c + dc >= M) continue;
                    for (int dr = -1; dr <= 1; dr++) {
                        if (r + dr < 0 || r + dr >= N) continue;
                        if (grid[r + dr][c + dc] == '.')
                            g.add_edge(r * M + c, (r + dr) * M + (c + dc), 1);
                    }
                }
            }
        }

        printf("Case #%d: %d\n", cur_case++, V - maxflow(g, s, t));
    }
    return 0;
}