#include<bits/stdc++.h>

#define uint unsigned int

#define rep(i,a,b) for(int i=a;i<=b;i++)

using namespace std;

const int maxn=;

char c[][]; bool vis[maxn];

int q[maxn],tot,N; uint dp[maxn];

void check(int S)

{

    rep(i,,S) vis[i]=,dp[i]=;

    dp[]=;

    rep(i,,S) {

        tot=; bool F=;

        rep(j,,N-) if(i&(<<j)) q[++tot]=j;

        rep(j,,tot){

            if(!F) break;

            rep(k,,tot)

             if(c[q[j]][q[k]]=='') {

                F=; break;

            }

        }

        if(F) vis[i]=;

    }

}

int main()

{

    int T,S;

    scanf("%d",&T);

    while(T--){

        scanf("%d",&N); S=(<<N)-;

        rep(i,,N-) scanf("%s",c[i]);

        check(S);

        for(int s=;s<=S;s++){

            for(int i=s;;i=(i-)&s){

                if(vis[i^s]){

                  dp[s]=min(dp[s],dp[i]+);

                }

                if(i==) break;

            }

        }

        uint t=,ans=;

        for(int i=;i<=S;i++){

            t=t*;

            ans+=t*dp[i];

        }

        cout<<ans<<endl;

    }

    return ;

}