#include<iostream>
#include<cstdio>
#include<vector>
#define N 1300000
using namespace std;
int read()
{
	char c=0;
	int sum=0;
	while (c<'0'||c>'9') c=getchar();
	while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
	return sum;
}
int T,n,len,leng,length,lengths,st,p[N+1],dst[N+1],num[N+1],lg[N+1],ST[N+1][21],sn[N+1][26],sa[N+1],rk[N+1],tp[N+1],h[N+1],ps[N+1],tong[N+1],delta[N+1],dp[N+1],sw[N+1],cnt[N+1],scnt[N+1],snum[N+1];
long long cs[N+1],ans;
char c[N+1];
string s[N+1];
vector<int>v[N+1];
int lowbit(int x)
{
	return x&(-x);
}
void add(int x,int d)
{
	for (;x<=len;x+=lowbit(x)) cs[x]+=d;
	return;
}
long long query(int x)
{
	long long res=0;
	for (;x>=1;x-=lowbit(x)) res+=cs[x];
	return res;
}
void build_SA()
{
	int x;
	for (int i=1;i<=27;++i) cnt[i]=0;
	for (int i=1;i<=length;++i) snum[i]=++cnt[c[i]-'`'+1];
	for (int i=1;i<=27;++i) scnt[i]=scnt[i-1]+(cnt[i]>0),cnt[i]+=cnt[i-1];
	for (int i=1;i<=length;++i) sa[cnt[c[i]-'`']+snum[i]]=i,rk[i]=scnt[c[i]-'`'+1];
	leng=scnt[27];
	for (int i=1;i<=length&&leng<length;i<<=1)
	{
		for (int j=1;j<=leng;++j) cnt[j]=0;
		for (int j=length-i+1;j<=length;++j) snum[j]=++cnt[rk[j]];
		for (int j=1;j<=length;++j)
			if (sa[j]>i)
				snum[sa[j]-i]=++cnt[rk[sa[j]-i]];
		for (int j=1;j<=leng;++j) cnt[j]+=cnt[j-1];
		for (int j=1;j<=length;++j) sa[cnt[rk[j]-1]+snum[j]]=j;
		leng=0;
		for (int j=1;j<=length;++j)
		{
			if (rk[sa[j]]!=rk[sa[j-1]]||(sa[j]+i<=length?rk[sa[j]+i]:0)!=(sa[j-1]+i<=length?rk[sa[j-1]+i]:0)) tp[j]=tp[j-1]+1;
			else tp[j]=tp[j-1];
		}
		for (int j=1;j<=length;++j) rk[sa[j]]=tp[j];
		leng=rk[sa[length]];
	}
	for (int i=1;i<=length;++i)
	{
		x=rk[i],h[x]=max(h[rk[i-1]]-1,0);
		if (x!=1)
		{
			while (max(sa[x-1],i)+h[x]<=length&&c[sa[x-1]+h[x]]==c[i+h[x]]) h[x]++;
		}
	}
	return;
}
int lcp(int x,int y)
{
	if (x==y) return length-x+1;
	x=rk[x],y=rk[y];
	if (x>y) swap(x,y);
	int lw=lg[y-x];
	return min(ST[x+1][lw],ST[y-(1<<lw)+1][lw]);
}
struct reads
{
	int l,r;
	bool operator < (const reads &t)const
	{
		int d=lcp(l,t.l);
		if (d>=min(r-l+1,t.r-t.l+1)) return r-l+1<t.r-t.l+1;
		else return c[l+d]<c[t.l+d];
	}
	bool operator <= (const reads &t)const
	{
		int d=lcp(l,t.l);
		if (d>=min(r-l+1,t.r-t.l+1)) return r-l+1<=t.r-t.l+1;
		else return c[l+d]<c[t.l+d];
	}
};
int find(reads x)
{
	int pst=0;
	for (int i=lg[len];i>=0;--i)
		if (pst+(1<<i)<=len&&(reads){st,st+pst+(1<<i)-1}<=x)
			pst+=(1<<i);
	return pst;
}
int calc(int d,reads x)
{
	int pst=0;
	for (int i=lg[d];i>=0;--i)
		if (pst+(1<<i)<=d&&(reads){num[tong[pst+(1<<i)]],num[tong[pst+(1<<i)]]+s[tong[pst+(1<<i)]].length()-1}<=x)
			pst+=(1<<i);
	return pst;
}
int main()
{
	int x,d,res,psw;
	for (int i=2;i<=N;++i) lg[i]=lg[i>>1]+1;
	T=read();
	while (T--)
	{
		n=read(),length=psw=0,lengths=1,ans=1ll*n*(n-1)*(n-2)/6;
		for (int i=1;i<=n;++i)
		{
			cin>>s[i],num[i]=length+1,ps[num[i]]=i,d=1;
			for (int j=0;j<s[i].length();++j)
			{
				c[++length]=s[i][j];
				if (!sn[d][s[i][j]-'a']) sn[d][s[i][j]-'a']=++lengths;
				d=sn[d][s[i][j]-'a'];
			}
			c[++length]='`';
		}
		build_SA();
		for (int i=1;i<=length;++i) ST[i][0]=h[i];
		for (int i=1;i<=lg[length];++i)
			for (int j=1;j+(1<<i)-1<=length;++j)
				ST[j][i]=min(ST[j][i-1],ST[j+(1<<(i-1))][i-1]);
		for (int i=1;i<=length;++i)
			if (ps[sa[i]])
				tong[++psw]=ps[sa[i]];
		for (int i=1;i<=n;++i)
		{
			x=tong[i],d=1,res=i-1,st=num[x],len=s[x].length();
			for (int j=0;j<s[x].length();++j) d=sn[d][s[x][j]-'a'],delta[j+1]=dp[d],res-=dp[d];
			for (int j=1;j<=s[x].length();++j) sw[j]=sw[j-1]+delta[j];
			for (int j=1;j<=s[x].length();++j) dst[j]=find((reads){num[x]+j,num[x]+s[x].length()-1}),ans-=1ll*delta[j]*(calc(i-1,(reads){num[x]+j,num[x]+s[x].length()-1})-sw[dst[j]]);
			for (int j=1;j<=s[x].length();++j)
				if ((reads){num[x],num[x]+j-1}<=(reads){num[x]+j,num[x]+s[x].length()-1})
					ans-=((1ll*delta[j]*(delta[j]-1))>>1);
			for (int j=1;j<=s[x].length();++j) v[j].clear(),cs[j]=0;
			for (int j=1;j<=s[x].length();++j) v[dst[j]].push_back(j);
			for (int j=1;j<=s[x].length();++j)
			{
				if (j+1<=dst[j]) add(j+1,delta[j]),add(dst[j]+1,-delta[j]);
				for (int k=0;k<v[j].size();++k) ans-=query(v[j][k])*delta[v[j][k]];
			}
			ans-=((1ll*res*(res-1))>>1),dp[d]++;
		}
		printf("%lld\n",ans);
		for (int i=1;i<=length;++i) ps[i]=0;
		for (int i=1;i<=lengths;++i)
		{
			dp[i]=0;
			for (int j=0;j<26;++j) sn[i][j]=0;
		}
	}
	return 0;
}