#include<bits/stdc++.h>
#define F(i,j,k) for(auto i=j;i<=(decltype(i))k;i++)
#define x first
#define y second
#define exec(...) [&](){__VA_ARGS__}()
#define endl '\n'
#define os ostream
#define pb push_back
#define view(x) begin(x),end(x)
#define lambda [&]
using namespace std;
using ll=long long;
template<typename T>void ckmin(T& x,T y){x=min(x,y);}
template<typename T>void ckmax(T& x,T y){x=max(x,y);}

#ifdef DEBUG
template<typename T1,typename T2>os& operator<<(os&,pair<T1,T2>);
template<typename T,typename=decltype(T().begin()),typename=enable_if_t<!is_same_v<decay_t<T>,string>>>os& operator<<(os& out,T x){auto n=0u;out<<"{";for(auto i:x) out<<i<<(++n==x.size()?"":",");return out<<"}";}
template<typename ...T>os& operator<<(os& out,tuple<T...> x){return apply(lambda(T... x){auto n=0u;out<<"{";((out<<x<<(++n==sizeof...(T)?"":",")),...);},x),out<<"}";}
template<typename T1,typename T2>os& operator<<(os& out,pair<T1,T2> x){return out<<tuple(x);}
#define debug(...) cerr<<"#"<<__LINE__<<": "<<#__VA_ARGS__<<" = "<<std::make_tuple(__VA_ARGS__)<<endl
#else
#define debug(...) (void)0
#endif

const int maxn=1.4e6+5;

char s[maxn];
int n,h[maxn],id[maxn],sa[maxn],rk[maxn],buc[maxn],m,p,rk0[maxn];
int st[__lg(maxn)+5][maxn];

void getsa(){
	m=130,p=0;
	F(i,1,n) buc[ rk[i]=s[i] ]++;
	F(i,1,m) buc[i]+=buc[i-1];
	for(int i=n;i>=1;i--) sa[ buc[rk[i]]-- ]=i;
	for(int w=1;p!=n;w*=2){
		m=p;
		p=0;
		F(i,1,n) if(i>=n-w+1) id[++p]=i;
		F(i,1,n) if(sa[i]>w) id[++p]=sa[i]-w;
		memset(buc,0,sizeof(buc[0])*(m+3));
		F(i,1,n) buc[ h[i]=rk[id[i]] ]++;
		F(i,1,m) buc[i]+=buc[i-1];
		for(int i=n;i>=1;i--) sa[ buc[h[i]]-- ]=id[i];
		p=0,memcpy(rk0,rk,sizeof rk);
		F(i,1,n) rk[sa[i]]=[w,x=sa[i-1],y=sa[i]](){return rk0[x]==rk0[y] && rk0[x+w]==rk0[y+w];}()? p: ++p;
	}
	F(_,1,n){
		int i=rk[_];
		st[0][i]=max(st[0][rk[_-1]]-1,0);
		while(s[sa[i]+st[0][i]]==s[sa[rk[sa[i]]-1]+st[0][i]]) st[0][i]++;
	}
	F(i,1,__lg(n)) F(j,1,n-(1<<i)+1) st[i][j]=min(st[i-1][j],st[i-1][j+(1<<(i-1))]);
	//F(i,1,n) debug(i,s+sa[i],st[0][i]);
	memset(buc,0,sizeof(int)*(m+3));
}

int get(int x,int y){
	if(x>y) return n-sa[y]+1;
	int d=__lg(y-x+1);
	return min(st[d][x],st[d][y-(1<<d)+1]);
}

int _lcp(int x,int y){
	if(x==y) return n-y+1;
	x=rk[x],y=rk[y];
	if(x>y) swap(x,y);
	return get(x+1,y);
}

int lcp(int x,int y){
	return _lcp(x,y);
	//int len=0;
	//while(x+len-1<=n && y+len-1<=n && s[x+len]==s[y+len]) len++;
	//assert(_lcp(x,y)==len);
	//return len;
}

bool _cmp(pair<int,int> a,pair<int,int> b){
	if(b.x>b.y) return 0;
	if(a.x>a.y) return 1;
	int len=lcp(a.x,b.x);
	if(a.x+len<=a.y && b.x+len<=b.y) return s[a.x+len]<s[b.x+len];
	return a.y-a.x < b.y-b.x;
}

bool cmp(pair<int,int> a,pair<int,int> b){
	bool ans=_cmp(a,b);
	//assert(ans==(string(s+a.x,s+a.y+1)<string(s+b.x,s+b.y+1)));
	return ans;
}

int getfst(pair<int,int> rng){
	if(rng.x>rng.y) return 0;
	int len=rng.y-rng.x+1;
	{
		int l=1,r=rk[rng.x]-1,z=rk[rng.x];
		while(l<=r){
			int mid=(l+r)>>1;
			if(get(mid+1,rk[rng.x])>=len) r=mid-1,z=mid;
			else l=mid+1;
		}
		return z;
	}
}

int getlst(pair<int,int> rng){
	if(rng.x>rng.y) return 1;
	int pos=sa[getfst(rng)];
	int len=rng.y-rng.x+1;
	rng={pos,pos+len-1};
	{
		int l=rk[rng.x],r=n,z=rk[rng.x]-1;
		while(l<=r){
			int mid=(l+r)>>1;
			if(get(rk[rng.x]+1,mid)>=len && s[sa[mid]+len]=='$') l=mid+1,z=mid;
			else r=mid-1;
		}
		return z;
	}
}

vector<pair<int,int>> pp;

int qzh[maxn];

int _f(int l,int r){return qzh[getfst({l,r})-1];}
int f(int l,int r){
	return _f(l,r);
	//int ans=0;
	//for(auto i:pp) if(string(s+i.x,s+i.y+1)<string(s+l,s+r+1)) ans++;
	//assert(ans==_f(l,r));
	//return ans;
}
int _c(int l,int r){return qzh[getlst({l,r})]-qzh[getfst({l,r})-1];}
int c(int l,int r){
	return _c(l,r);
	//int ans=0;
	//for(auto i:pp) if(string(s+i.x,s+i.y+1)==string(s+l,s+r+1)) ans++;
	//assert(ans==_c(l,r));
	//return ans;
}

ll ans;

void solve(int l,int r){
	int cx=c(l,r),fx=f(l,r);
	debug("solve",l,r);
	debug(1ll*(cx-1)*(cx-2) + 3ll*(cx-1)*fx);
	ans+=1ll*(cx-1)*(cx-2) + 3ll*(cx-1)*fx;
	vector<pair<pair<int,int>,int>> v;
	F(i,l,r-1){
		int cy=c(l,i);
		ans+=6ll*cy*max(0,fx-f(i+1,r)-c(i+1,r));
		if(cmp({i+1,r},{l,i})) ans-=3ll*cy*(cy+1);
		v.pb({{getfst({l,i}),getfst({i+1,r})},cy});
	}
	F(i,0,v.size()-1) F(j,i+1,v.size()-1){
		auto a=v[i].x,b=v[j].x;
		if(a.x>b.y && b.x>a.y) ans-=6ll*v[i].y*v[j].y;
	}
}

void doit(){
	ans=0;
	memset(s,0,sizeof(int)*(n+3));
	memset(h,0,sizeof(int)*(n+3));
	memset(qzh,0,sizeof(int)*(n+3));
	memset(id,0,sizeof(int)*(n+3));
	memset(sa,0,sizeof(int)*(n+3));
	memset(rk,0,sizeof(int)*(n+3));
	memset(buc,0,sizeof(int)*(n+3));
	memset(rk0,0,sizeof(int)*(n+3));
	for(auto& i:st) memset(i,0,sizeof(int)*(n+3));
	n=0;
	int p;
	cin>>p;
	pp.clear();
	F(i,1,p){
		char ss[maxn];
		cin>>(ss+1);
		int len=strlen(ss+1);
		s[++n]='$';
		F(j,1,len) s[++n]=ss[j];
		pp.pb({n-len+1,n});
	}
	s[++n]='$';
	s[++n]='|';
	getsa();
	for(auto i:pp) qzh[rk[i.x]]++;
	F(i,1,n) qzh[i]+=qzh[i-1];
	for(auto i:pp) solve(i.x,i.y);
	debug(ans);
	cout<<ans/6<<endl;
}

signed main(){
	cin.tie(0)->sync_with_stdio(0);
	int t;
	cin>>t;
	while(t--) doit();
}