#pragma comment(linker, "/STACK:1024000000,1024000000")

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<vector>

#include<map>

#include<set>

#include<queue>

#include<stack>

#include<iostream>

using namespace std;

typedef long long LL;

const double pi=acos(-1.0),eps=1e-;

void File()

{

    freopen("D:\\in.txt","r",stdin);

    freopen("D:\\out.txt","w",stdout);

}

inline int read()

{

    char c = getchar(); while(!isdigit(c)) c = getchar(); int x = ;

    while(isdigit(c)) { x = x *  + c - ''; c = getchar();  }

    return x;

}

const int maxn=;

char s[maxn];

int T,n,e[],f[];

bool t[];

LL mod=((LL)<<);

LL POW(LL a,LL b,LL MOD){

    LL ret=;

    while(b){ if(b&) ret=(ret*a)%MOD; a=(a*a)%MOD; b>>=; }

    return ret;

}

int main()

{

    scanf("%d",&T); while(T--)

    {

        scanf("%d",&n);

        memset(e,,sizeof e); memset(t,,sizeof t);

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

        {

            scanf("%s",s);

            for(int j=;s[j];j++) if(s[j]=='')  e[i]=e[i]|(<<j);

        }

        t[]=;

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

        {

            if(t[i]==) continue;

            int state=i; for(int j=;j<n;j++) if(i&(<<j)) state=state|e[j];

            for(int j=;j<n;j++) if(!(state&(<<j))) t[i|(<<j)]=;

        }

        f[]=;

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

        {

            f[i]=;

            for(int j=i;j;j=(j-)&i) if(t[j]) f[i]=min(f[i],f[i^j]+);

        }

        LL ans=,P=;

        for(int i=;i<(<<n);i++) ans=(ans+f[i]*P%mod)%mod, P=P*%mod;

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

    }

    return ;

}