#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<random>
#include<chrono>
typedef long long ll;
typedef unsigned un;
typedef std::vector<int> P;
typedef std::pair<int,int> pii;
ll read(){ll x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();return f*x;}
ll max(ll a,ll b){return a>b?a:b;}
ll min(ll a,ll b){return a<b?a:b;}
template <typename T> bool umax(T& a,T t){if(t>a)return a=t,1;return 0;}
template <typename T> bool umin(T& a,T t){if(t<a)return a=t,1;return 0;}
/**********/
const int MAXN = 1011,MAXM = 5011;
const int INF = 1e9+233;
namespace Flow
{
    struct edge{int v,w,nxt;}e[MAXM<<1|1];
    int cnt=1,last[MAXN],cur[MAXN];
    void add_directed_edge(int u,int v,int w){e[++cnt].v=v,e[cnt].w=w,e[cnt].nxt=last[u],last[u]=cnt;}
    void adde(int u,int v,int w){ add_directed_edge(u,v,w),add_directed_edge(v,u,0);}
    int Q[MAXN],dep[MAXN];
    bool bfs(int st,int ed,int n)
    {
        for(int i=1;i<=n;++i)cur[i]=last[i],dep[i]=0;
        int h=0,t=0;
        Q[t++]=st,dep[st]=1;
        while(h<t)
        {
            int u=Q[h++];
            for(int i=last[u];i;i=e[i].nxt)
            {
                int v=e[i].v;
                if(e[i].w&&!dep[v])dep[v]=dep[u]+1,Q[t++]=v;
            }
        }
        return dep[ed];
    }
    int ex_flow(int u,int t,int flow=INF)
    {
        if(u==t)return flow;
        int f=0;
        for(int &i=cur[u];i;i=e[i].nxt)
        {
            int v=e[i].v;
            if(e[i].w&&dep[v]==dep[u]+1)
            {
                int tmp=ex_flow(v,t,min(e[i].w,flow-f));
                e[i].w-=tmp,e[i^1].w+=tmp;
                f+=tmp;
                if(f==flow)return f;
            }
        }
        return f;
    }
    void clear(int n)
    {
        cnt=1;
        for(int i=1;i<=n;++i)last[i]=0;
    }
    int Dinic(int s,int t,int n)
    {
        int res=0;
        while(bfs(s,t,n))res+=ex_flow(s,t);
        return res;
    }
}

char a[MAXN][MAXN];
int main()
{
    int task=read();
    while(task--)
    {
        int n=read(),S=n*n+1,T=2*n*n;
        for(int i=1;i<=n;++i)scanf("%s",a[i]+1);
        if(a[1][1]=='#'||a[n][n]=='#'){puts("0");continue;}
        for(int i=1;i<=n;++i)
            for(int j=1;j<=n;++j)
            {
                int cur=(i-1)*n+j;
                if(a[i][j]=='.')Flow::adde(cur,cur+n*n,((i==1&&j==1)||(i==n&&j==n)?INF:1));
                if(i<n)Flow::adde(cur+n*n,cur+n,INF);
                if(j<n)Flow::adde(cur+n*n,cur+1,INF);
            }
        printf("%d\n",Flow::Dinic(S,T,T));
        Flow::clear(T);
    }
    return 0;
}