#include <cstdio>
#include <cstring>

#define MAXN 360010
#define MAXM 2000000

using namespace std;

struct edge
{
    int to;
    edge *next;
} e[MAXM], *vert[MAXN];

char mp[610][610];
int dx[4] = {-1,0,1,0};
int dy[4] = {0,-1,0,1};
int y[MAXN];
int bl[MAXN], N;
bool mk[MAXN];

void addedge(int u, int v, int &top)
{
    edge *p = &e[++top];
    p->to = v, p->next = vert[u], vert[u] = p;
}

bool dfs(int u)
{
    for (edge *p = vert[u]; p; p = p->next)
    {
        int v = p->to;
        if (!mk[v])
        {
            mk[v] = 1;
            if (y[v] == -1 || dfs(y[v]))
            {
                y[v] = u;
                return 1;
            }
        }
    }
    return 0;
}

int solve()
{
    int ret = 0;
    memset(y, -1, sizeof(y));
    for (int i = 0; i < N; ++i)
    {
        memset(mk, 0, sizeof(mk));
        if (dfs(bl[i])) ++ret;
    }
    return ret;
}

void init()
{
    int cas, n;
    scanf("%d", &cas);
    for (int T = 1; T <= cas; ++T)
    {
        scanf("%d", &n);
        for (int i = 0; i < n; ++i)
            scanf("%s", mp[i]);
        N = 0;
        int top = -1;
        memset(vert, 0, sizeof(vert));
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                if (mp[i][j] == '#' && (i+j)&1)
                {
                    bl[N++] = i*n+j;
                    for (int k = 0; k < 4; ++k)
                    {
                        int tx = i + dx[k], ty = j + dy[k];
                        if (tx >= 0 && tx < n && ty >= 0 && ty < n && mp[tx][ty]=='#')
                            addedge(i*n+j, tx*n+ty, top);
                    }
                }
        int ans = solve();
        printf("Case %d: %d\n", T, ans);
    }
}

int main()
{
    init();
    return 0;
}
