#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define SZ(x) ((int)x.size())
#define L(i,u) for (register int i=head[u]; i; i=nxt[i])
#define rep(i,a,b) for (register int i=(a); i<=(b); i++)
#define per(i,a,b) for (register int i=(a); i>=(b); i--)
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef pair<int,int> Pii;
typedef vector<int> Vi;
template<class T> inline void read(T &x){
    x=0; char c=getchar(); int f=1;
    while (!isdigit(c)) {if (c=='-') f=-1; c=getchar();}
    while (isdigit(c)) {x=x*10+c-'0'; c=getchar();} x*=f;
}
template<class T> inline void umin(T &x, T y){x=x<y?x:y;}
template<class T> inline void umax(T &x, T y){x=x>y?x:y;}
inline ui R() {
    static ui seed=416;
    return seed^=seed>>5,seed^=seed<<17,seed^=seed>>13;
}
const int N = 1015;
int n,l[N];char s[12][N];
int bh[12][N],num;Pii dy[N];
ll dp[1<<10|3][N][2];
int ch[1002*1003][26],tot;
struct Trie{
    int f[N][N];
    void ini(bool flip){
        rep(t,1,n)rep(a,1,l[t]){
            int cur=0;rep(b,a,l[t]){
                int c=s[t][!flip?b:l[t]-b+1]-'a';
                assert(c>=0&&c<26);
                if(!ch[cur][c])ch[cur][c]=++tot;
                cur=ch[cur][c];f[bh[t][a]][bh[t][b]]=cur;
            }
        }
    }
}c[2];
inline int getval(int tp, int i, int l, int r){
    return c[tp].f[bh[i][l]][bh[i][r]];
}
inline int getval(int i, int L, int R){
    if(L<=R)return getval(0,i,L,R);
    return getval(1,i,l[i]-L+1,l[i]-R+1);
}
int main() {
    int T;read(T);while(T--){
        read(n);rep(i,1,n){
            scanf("%s",s[i]+1);l[i]=strlen(s[i]+1);
        }
        num=0;
        rep(i,1,n)rep(j,0,l[i])bh[i][j]=++num,dy[num]=Pii(i,j);
        rep(i,0,tot)memset(ch[i],0,sizeof(ch[i]));tot=0;
        c[0].ini(0);c[1].ini(1);
    //    rep(t,0,1)rep(i,1,n)rep(a,1,l[i])rep(b,a,l[i])printf("%d %d %d %d:%d\n",t,i,a,b,getval(t,i,a,b));
        int all=(1<<n)-1;
        rep(i,0,all)rep(j,0,num)rep(k,0,1)dp[i][j][k]=0;
        rep(i,1,n)dp[1<<i-1][bh[i][0]][0]=dp[1<<i-1][bh[i][0]][1]=1;
        ll res=0;
        rep(s,0,all)rep(j,0,num)rep(k,0,1)if(dp[s][j][k]){
            if(!k){
                int i=dy[j].fi,len=dy[j].se;
            //    cerr<<i<<' '<<len<<' '<<getval(i,len+1,l[i])<<' '<<getval(i,l[i],len+1)<<endl;
                if(len==l[i]||getval(i,len+1,l[i])==getval(i,l[i],len+1))res+=dp[s][j][k];
            }
            else{
                int i=dy[j].fi,len=dy[j].se;
                if(len==l[i]||getval(i,1,l[i]-len)==getval(i,l[i]-len,1))res+=dp[s][j][k];
            }
            int x=dy[j].fi,y=dy[j].se;
            rep(i,1,n)if(!(s>>i-1&1))rep(p,0,1){
                if(l[x]-y>=l[i]){
                    if(getval(k,dy[j].fi,dy[j].se+1,dy[j].se+l[i])==getval(p,i,1,l[i]))
                        dp[s|(1<<i-1)][bh[x][y+l[i]]][k]+=dp[s][j][k];
                }
                else{
                    if(getval(k,x,y+1,l[x])==getval(p,i,1,l[x]-y))
                        dp[s|(1<<i-1)][bh[i][l[x]-y]][p]+=dp[s][j][k];
                }
            }
        }
        printf("%lld\n",res);
    }
    return 0;
}