#include<bits/stdc++.h>
#define inl inline
using namespace std;
typedef long long ll;
const int N=4e5+5,IB=1<<21; char IN[IB],*IS=IN+IB,*IT=IS;
#define gc() (IS==IT&&(IT=IN+fread(IS=IN,1,IB,stdin)),IS==IT?EOF:*IS++)
int T,n,dc,la,a[N],fa[N],le[N],ch[N][26],d[N],vs[N];
ll an; queue<int> q; vector<int> e[N]; set<int> s[N],f[N];
inl int RD()
{
	int s=0; char c; while(!isdigit(c=gc()));
	for(;isdigit(c);s=s*10+c-48,c=gc()); return s;
}
inl void Ins(int v)
{
	int p=++dc,f=la,q,t; le[la=p]=le[f]+1; for(;!ch[f][v];ch[f][v]=p,f=fa[f]);
	if(!f) {fa[p]=1; return; } if(le[q=ch[f][v]]==le[f]+1) {fa[p]=q; return; }
	le[t=++dc]=le[f]+1; fa[t]=fa[q]; fa[q]=fa[p]=t; memcpy(ch[t],ch[q],sizeof(ch[t]));
	for(;ch[f][v]==q;ch[f][v]=t,f=fa[f]);
}
inl void MG(int x,int y)
{
	s[x].size()<s[y].size()&&(swap(s[x],s[y]),swap(f[x],f[y]),0);
	for(int u:s[y])
	{
		auto i=s[x].insert(u).first,j=i,k=i; ++k;
		if(k==s[x].end()) j!=s[x].begin()&&(f[x].insert(u-*--j),0);
		else j!=s[x].begin()&&(f[x].erase(*k-*--j),f[x].insert(u-*j),0), f[x].insert(*k-u);
	}
}
int main()
{
	for(T=RD();T--;printf("%lld\n",an),an=0)
	{
		for(int i=0;i<N;vs[i++]=0) s[i].clear(), f[i].clear(), e[i].clear();
		memset(ch,0,sizeof(ch)); la=dc=1; char c; while(!isalpha(c=gc()));
		for(n=0;isalpha(c);Ins(a[++n]=c-97),s[la].insert(n),c=gc());
		for(int i=2;i<=dc;++i) ++d[fa[i]], e[fa[i]].push_back(i);
		for(int i=1;i<=dc;++i) !d[i]&&(q.push(i),0);
		for(int u,l,r,v,j;!q.empty();q.pop()) if((u=q.front())>1)
		{
			sort(e[u].begin(),e[u].end(),[](int x,int y){return s[x].size()>s[y].size(); });
			l=le[fa[u]]+1; r=le[u]; an+=r-l+1; for(int v:e[u]) MG(u,v);
			for(int t;!f[u].empty()&&(t=*f[u].rbegin())>r;f[u].erase(t));
			for(auto i=f[u].begin();i!=f[u].end();) if(vs[v=*i]==u) i=f[u].erase(i);
			else for(++i,j=(l-1)/v*v+v;j<=r;j+=v) vs[j]!=u&&(--an,vs[j]=u);
			!--d[fa[u]]&&(q.push(fa[u]),0);
		}
	}
	return 0;
}