#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1.5e6 + 10;//2*strlen
struct Suffix{
	int ht[N],rk[N],sa[N],y[N],c[N];
    int n,m;
    char s[N];
    int st[22][N];
	void init(){
        n=strlen(s+1);
        m=300;
		for(int i=0;i<=m;i++) c[i]=0;
		for(int i=0;i<=2*n;i++) y[i]=0;
		for(int i=1;i<=n;i++) c[rk[i]=s[i]]++;
		for(int i=1;i<=m;i++) c[i]+=c[i-1];
		for(int i=n;i>=1;i--) sa[c[rk[i]]--]=i;
		for(int k=1;k<=n;k<<=1){
			int p=0;
			for(int i=n-k+1;i<=n;i++) y[++p]=i;
			for(int i=1;i<=n;i++){
				if(sa[i]>k){
					y[++p]=sa[i]-k;
				}
			} 
			for(int i=0;i<=m;i++) c[i]=0;
			for(int i=1;i<=n;i++) c[rk[i]]++;
			for(int i=1;i<=m;i++) c[i]+=c[i-1];
			for(int i=n;i>=1;i--) sa[c[rk[y[i]]]--]=y[i];
			for(int i=0;i<=n;i++) swap(rk[i],y[i]);
			rk[sa[1]]=p=1;
			for(int i=2;i<=n;i++){
				rk[sa[i]]=(y[sa[i]] == y[sa[i-1]] && y[sa[i]+k] == y[sa[i-1]+k] ? p : ++p);
			}
			if(p>=n) break;
			m=p;
		}
		for(int i=1,k=0;i<=n;i++){
			if(k)k--;
			int j=sa[rk[i]-1];
			while(s[i+k] == s[j+k] )k++;
			ht[rk[i]] = k;
		}
        for(int i=1;i<=n;i++)st[0][i]=ht[i];
        for(int j=1;j<22;j++){
            for(int i=1;i+(1<<j)-1<=n;i++)st[j][i]=min(st[j-1][i],st[j-1][i+(1<<(j-1))]);
        }
	}
    int get(int l,int r){
        int g=__lg(r-l+1);
        return min(st[g][l],st[g][r-(1<<g)+1]);
    }
    int lcp(int x,int y){
        x=rk[x],y=rk[y];
        if(x==y)return n-x+1;
        if(x>y)swap(x,y);
        return get(x+1,y);
    }
    int query(int l1,int r1,int l2,int r2){
        int len=lcp(l1,l2);
        len=min({len,r1-l1+1,r2-l2+1});
        if(len==min(r1-l1+1,r2-l2+1)){
            if(r1-l1>r2-l2)return 1;
            if(r1-l1<r2-l2)return -1;
            if(r1-l1==r2-l2)return 0;
        }
        char p=s[l1+len],q=s[l2+len];
        if(p>q)return 1;
        if(p==q)return 0;
        return -1;
    }
    void writ()
    {
        printf("%s\n",s+1);
        for(int i=1;i<=n;i++)cout<<sa[i]<<" ";;cout<<"\n";
        for(int i=1;i<=n;i++)cout<<ht[i]<<" ";;cout<<"\n";
        for(int i=1;i<=n;i++)cout<<rk[i]<<" ";;cout<<"\n";
    }
    
};
Suffix suf;
struct Trie {
    int tree[N][26],tot=0;
    int e[N],id[N],sum[N],dep[N],dfn[N];
    int mx[N],mi[N];
    int now=0;
    Trie(){
        memset(e,0,sizeof(e));
        memset(id,-1,sizeof(id));
        memset(mx,-1,sizeof(mx));
        memset(mi,0x3f,sizeof(mi));
    }
    void clear(){
        for(int i=0;i<=tot;i++){
            memset(tree[i],0,sizeof(tree[i]));
            e[i]=0;
            id[i]=-1;
            sum[i]=0;
            dep[i]=0;
            mi[i]=1e9;
            mx[i]=-1;
        }
        tot=0;now=0;
    }
    int insert(string &t,int idd,int v){
        int x=0;
        for(int i=0;i<t.size();i++){
            if(!tree[x][t[i]-'a']){
                tree[x][t[i]-'a']=++tot;
                dep[tot]=dep[x]+1;
            }            
            x=tree[x][t[i]-'a'];
            sum[x]+=v;
        }
        e[x]+=v;
        if(v>0){
            id[x]=idd;
            mx[x]=max(mx[x],idd);
            mi[x]=min(mi[x],idd);
        }
        return dfn[x];
    }
    void dfs(int x){
        dfn[x]=++now;
        for(int i=0;i<26;i++)if(tree[x][i])dfs(tree[x][i]);
    }
};
Trie tri;
ll solve()
{
    int n;cin>>n;
    tri.clear();
    vector<string>s(n);
    vector<int> l(n),r(n);
    int now=0;
    vector<int> id_tree(n);
    for(int i=0;i<n;i++){
        cin>>s[i];
        id_tree[i]=tri.insert(s[i],i,0);
        l[i]=now+1;
        for(auto &it:s[i]){
            now++;
            suf.s[now]=it;
        }
        r[i]=now;
        suf.s[++now]='#';
    }
    tri.dfs(0);
    for(int i=0;i<n;i++)id_tree[i]=tri.insert(s[i],i,0);
    vector<int> id(n);iota(id.begin(),id.end(),0);
    sort(id.begin(),id.end(),[&](int x,int y){
        return id_tree[x]<id_tree[y];
    });
    for(int i=0;i<n;i++)tri.insert(s[id[i]],i,1);
    suf.s[now+1]=0;
    suf.init();
    // suf.writ();
    int havvis=0;
    ll ans1=0,ans2=0,ans3=0,ans4=0,ans5=0,ans6=0;
    auto dfs = [&](auto&& self,int x,vector<int> &lis) -> void {
        if(tri.e[x]){
            for(int i=0;i<lis.size();i++){
                int it=lis[i];
                int rlen=tri.dep[x]-tri.dep[it];
                int rL=r[id[tri.id[x]]]-rlen+1,rR=r[id[tri.id[x]]];
                {//ans4
                    if(suf.query(l[id[tri.id[it]]],r[id[tri.id[it]]],rL,rR)>0)
                        ans4+=(ll)tri.e[it]*(tri.e[it]-1)/2*tri.e[x];
                }
                {//ans1
                    int ql=tri.mx[it]+1,qr=tri.mi[x]-1,res=tri.mi[x];
                    while(ql<=qr){
                        int mid=(ql+qr)/2;
                        if(suf.query(l[id[mid]],r[id[mid]],rL,rR)>0){
                            res=mid;qr=mid-1;
                        }
                        else ql=mid+1;
                    }
                    ans1+=(ll)tri.e[it]*(tri.mi[x]-res)*tri.e[x];
                }
                {//ans2
                    int ql=0,qr=tri.mi[it]-1,res=tri.mi[it];
                    while(ql<=qr){
                        int mid=(ql+qr)/2;
                        if(suf.query(l[id[mid]],r[id[mid]],rL,rR)>0){
                            res=mid;qr=mid-1;
                        }
                        else ql=mid+1;
                    }
                    ans1+=(ll)tri.e[it]*(tri.mi[it]-res)*tri.e[x];
                }
                {//ans3
                    for(int j=i+1;j<lis.size();j++){
                        int it2=lis[j];
                        if(suf.query(l[id[tri.id[it2]]],r[id[tri.id[it2]]],rL,rR)>0){
                            int plen=tri.dep[x]-tri.dep[it2];
                            int pL=r[id[tri.id[x]]]-plen+1,pR=r[id[tri.id[x]]];
                            if(suf.query(l[id[tri.id[it]]],r[id[tri.id[it]]],pL,rR)>0){
                                ans3+=(ll)tri.e[it]*tri.e[it2]*tri.e[x];
                            }
                        }
                    }
                }
            }
            ans5+=(ll)tri.e[x]*(tri.e[x]-1)/2*havvis;
            ans6+=(ll)tri.e[x]*(tri.e[x]-1)*(tri.e[x]-2)/6;

            lis.push_back(x);
        }
        havvis+=tri.e[x];
        for(int i=0;i<26;i++)if(tri.tree[x][i])self(self,tri.tree[x][i],lis);
        if(tri.e[x])lis.pop_back();        
    };
    vector<int>lis;
    dfs(dfs,0,lis);
    // cout<<"ans1="<<ans1<<" ans2="<<ans2<<" ans3="<<ans3<<" ans4="<<ans4<<" ans5="<<ans5<<" ans6="<<ans6<<endl;
    return ans1+ans2-ans3+ans4+ans5+ans6;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;cin>>T;
    while(T--)cout<<solve()<<"\n";
    return 0;
}