#include <cstdio>
#include <cstring>
#include <algorithm>
const int N=1005,dx[]={0,1},dy[]={1,0};
struct LnkNode{
    int v,w,nxt;
}edge[N<<1];
int etot,fst[N],cur[N];
void addedge_(int u,int v,int w){
    ++etot;
    edge[etot].v=v;
    edge[etot].w=w;
    edge[etot].nxt=fst[u];
    fst[u]=etot;
}
void addedge(int u,int v,int w=1){addedge_(u,v,w),addedge_(v,u,0);}
int T,n,idc,s,t,id[15][15][2];
char a[15][15];
int q[N],Head,Tail,d[N];
bool bfs(){
    Head=Tail=0;
    memset(d+1,0xff,idc<<2);
    d[q[Tail++]=s]=1;
    while(Head<Tail){
        int x=q[Head++];
        for(int i=fst[x];i;i=edge[i].nxt){
            int &y=edge[i].v,&w=edge[i].w;
            if(w && d[y]==-1)
                d[q[Tail++]=y]=d[x]+1;
        }
    }
    return d[t]!=-1;
}
int dfs(int x,int f){
    if(x==t)
        return f;
    int r=f;
    for(int &i=cur[x];i;i=edge[i].nxt){
        int &y=edge[i].v,&w=edge[i].w;
        if(w && d[y]==d[x]+1){
            int k=dfs(y,std::min(w,r));
            w-=k,edge[i^1].w+=k;
            if(!(r-=k))
                break;
        }
    }
    return f-r;
}
int main(){
    scanf("%d",&T);
    while(T--){
        idc=0;
        scanf("%d",&n);
        for(int i=1;i<=n;++i){
            scanf("%s",a[i]+1);
            for(int j=1;a[i][j];++j)
                if(a[i][j]=='.')
                    id[i][j][0]=++idc,id[i][j][1]=++idc;
                else
                    id[i][j][0]=id[i][j][1]=0;
        }
        s=++idc,t=++idc;
        etot=1,memset(fst+1,0,idc<<2);
        for(int i=1;i<=n;++i)
            for(int j=1;j<=n;++j)
                if(id[i][j]){
                    addedge(id[i][j][0],id[i][j][1]);
                    for(int k=0;k<2;++k)
                        if(id[i+dx[k]][j+dy[k]])
                            addedge(id[i][j][1],id[i+dx[k]][j+dy[k]][0]);
                }
        if(id[1][1])
            addedge(s,id[1][1][1],0x7fffffff);
        if(id[n][n])
            addedge(id[n][n][0],t,0x7fffffff);
        int f,mf=0;
        while(bfs()){
            memcpy(cur+1,fst+1,idc<<2);
            while((f=dfs(s,0x7fffffff)))
                mf+=f;
        }
        printf("%d\n",mf);
    }
    return 0;
}