#include<bits/stdc++.h>

 using namespace std;

 int f[],q[],n,t;

 bool v[];

 char a[][];

 unsigned int d[];

 void dfs(int i,int st,bool ff)

 {

     if (i==n) v[st]=ff;

     else {

         dfs(i+,st,ff);

         if (ff)

         {

             for (int j=; j<=t; j++)

                 if (a[q[j]][i]=='') {ff=;break;}

         }

         q[++t]=i;

         dfs(i+,st|(<<i),ff);

         t--;

     }

 }

 int main()

 {

     int cas;

     scanf("%d",&cas);

     d[]=;

     for (int i=; i<(<<); i++) d[i]=d[i-]*;

     while (cas--)

     {

         scanf("%d",&n);

         for (int i=; i<n; i++)

             scanf("%s",a[i]);

         int m=<<n;t=;

         memset(v,,sizeof(v));

         dfs(,,);

         for (int i=; i<m; i++) f[i]=n;

         f[]=;

         for (int i=; i<m; i++)

             for (int j=i; j; j=(j-)&i)

                 if (v[j]) f[i]=min(f[i],f[i-j]+);

         unsigned int ans=;

         for (int i=; i<m; i++) ans+=d[i]*f[i];

         printf("%u\n",ans);

     }

 }