#include<bits/stdc++.h>
namespace ifzw{
#define ll long long
#define dd double
#define LL __int128
#define ull unsigned ll
#define siz(A) ((int)A.size())
using namespace std;
char gc(){static char buf[1<<16],*s,*t;if(s==t){t=(s=buf)+fread(buf,1,1<<16,stdin);if(s==t)return EOF;}return *s++;}
//#define getchar gc
ll read()
{
	char c;
	ll w=1;
	while((c=getchar())>'9'||c<'0')if(c=='-')w=-1;
	ll ans=c-'0';
	while((c=getchar())>='0'&&c<='9')ans=(ans<<1)+(ans<<3)+c-'0';
	return ans*w;
}
void pc(char c,int op)
{
	static char buf[1<<16],*s=buf,*t=(buf+(1<<16));
	(op||((*s++=c)&&(s==t)))&&(fwrite(buf,1,s-buf,stdout),s=buf);
}
void wt(int x)
{
	if(x>9)wt(x/10);
	pc('0'+x%10,0); 
}
void wts(int x,char op)
{
	if(x<0)pc('-',0),x=-x;
	wt(x),pc(op,0);
}
char ST;
namespace TRIE
{
	//为了方便，每层都开满也是可以的，为了好写，可以尝试说最下层开到 0 然后向上每次层 +1 。 
	//多一点。 
	//最高是第 0 层 
	//第 4 层是底层 (1e7层了) 
	//[ i 64, (i+1) 64 )
	// << 6 = *64 
	//注意，upd 都传序号（该层的第 x 个） 
	// t 存的是当前这个点的 64 个儿子是否有 1 情况，各个儿子分别对应左移 6 + 0~63 
	ull lin[272158],*p;
	ull *t[6];
	int B=4;
	void cls(int n)
	{
		++n;
		B=0,p=lin;
		int nw=1;
		while(nw<=n)
			t[B++]=p,p+=nw,nw*=64;
		memset(lin,0,sizeof(lin[0])*(p-lin+1));
	}
	//当前改好了，更新上一层。 
	void upd(int x,ull s,int dep=B)
	{
		if(dep==0)return;//从扔信息的角度写 
		t[dep-1][x>>6]|=(s<<(x&63));
		t[dep-1][x>>6]&=((-1ull)-((ull)(!s)<<(x&63)));
		upd(x>>6,t[dep-1][x>>6]!=0,dep-1);
	}
	//有那么一点离谱，要上去再下来。 
	int Pr(int x,int s,int dep=B-1)
	{
		if(dep<0)return -1;
		if(dep==B)return x;
		if(t[dep][x]&((s==64?0:(1ull<<s))-1))return Pr(x<<6|(63-__builtin_clzll(t[dep][x]&((s==64?0:(1ull<<s))-1))),64,dep+1);
		return Pr(x>>6,x&63,dep-1);
	}
	int Sf(int x,int s,int dep=B-1)
	{
		if(dep<0)return -1;
		if(dep==B)return x;
		if(s!=63&&t[dep][x]>>(s+1)<<(s+1))return Sf(x<<6|(__builtin_ctzll(t[dep][x]>>(s+1)<<(s+1))),-1,dep+1);
		return Sf(x>>6,x&63,dep-1);
	}
	int one(int x){return t[B-1][x>>6]>>(x&63)&1;}
	int Pr(int x){return Pr(x>>6,x&63);}
	int Sf(int x){return Sf(x>>6,x&63);}
};
//vector 建边 
const int xx=2e5+5;
struct nod
{
	int siz,link,to[26];
}e[xx<<1];
int lst,cst,n,ed[xx<<1];
char s[xx];
void add(int x)
{
	int now=++cst,p=lst;e[now].siz=e[lst].siz+1,lst=now;
	while(p&&!e[p].to[x])e[p].to[x]=now,p=e[p].link;
	if(!p)e[now].link=1;
	else 
	{
//		cerr<<"@\n";
		int q=e[p].to[x];
		if(e[q].siz==e[p].siz+1)e[now].link=q;
		else 
		{
			int s=++cst;e[s].siz=e[p].siz+1;
			for(int i=0;i<26;i++)e[s].to[i]=e[q].to[i];
			e[s].link=e[q].link;
			e[q].link=e[now].link=s;
			while(p&&e[p].to[x]==q)e[p].to[x]=s,p=e[p].link;
		}
	}
}
//vector 建边 
vector<int>v[xx<<1];
int siz[xx<<1],son[xx<<1];
//虚点个数是 endpos 的虚树。 
void dfs(int x,int y)
{
	siz[x]=(ed[x]!=0),son[x]=0;
	int mx=-1;
	for(auto to:v[x])
	{
		dfs(to,x);
		if(mx<siz[to])mx=siz[to],son[x]=to;
		siz[x]+=siz[to];
	}
//	cerr<<x<<" "<<siz[x]<<" "<<son[x]<<"^\n";
}

vector<int>all;
void get(int x)
{
//	cerr<<x<<"%\n";
	if(ed[x])all.push_back(ed[x]);
	for(auto to:v[x])get(to);
}

ll tdis;
int pr[xx];
vector<array<int,2> >lin[xx<<1];
//哪些 end 和 pr 是什么。 
priority_queue<array<int,2>,vector<array<int,2> >,greater<array<int,2> > >q;
//len 时刻，哪个 end 被覆盖 
//出来时记得清空 

//不好处理删除对之后的影响，考虑在取元素时重新查询并加入堆。 

ll ans;
void solve(int x,int len)
{
//	cerr<<x<<"@@@\n";
	//先处理 (len,end] 当前 
	int til=e[x].siz;
	while(siz(q)&&q.top()[0]<=til)
	{
		ans+=(q.top()[0]-1-len)*tdis;
		len=q.top()[0]-1;
		int nt=len+1,id=q.top()[1];
//		cerr<<nt<<"$\n";
		q.pop();
		if(pr[id]!=-1)
		{
			if(nt==1)
			{
				int to=TRIE::Pr(pr[id]);
				tdis-=(id-1-pr[id]),pr[id]=to==id-1?pr[to]:id-1,tdis+=(id-1-pr[id]);
//				cerr<<tdis<<" "<<id<<" "<<pr[id]<<" "<<nt<<" "<<to<<" "<<pr[id]<<"@\n";
				to=TRIE::Pr(pr[id]);
				if(to!=-1)q.push({pr[id]-to+1,id});
			}
			else 
			{
				int to=TRIE::Pr(pr[id]);
				if(to!=-1)
				{
					assert(to+nt-1<=pr[id]);
					//有可能重复覆盖，重复覆盖也满足 
					if(to+nt-1<pr[id])q.push({pr[id]-to+1,id});
					else 
					{
						tdis-=(id-1-pr[id]),pr[id]=pr[to],tdis+=(id-1-pr[id]);
						to=TRIE::Pr(pr[id]);
						if(to!=-1)q.push({pr[id]-to+1,id});
					}
					//相等从左往右 
				}
			}
		}
	}
//	for(int i=0;i<=n;i++)cerr<<i<<" "<<pr[i]<<"#\n";
//	cerr<<x<<" "<<tdis<<" "<<til<<"#sss\n";
	ans+=(til-len)*tdis,len=til;
//	cerr<<x<<" "<<son[x]<<"$%/"
	if(!son[x])
	{
		priority_queue<array<int,2>,vector<array<int,2> >,greater<array<int,2> > >().swap(q);
		tdis=0;int to;
		while((to=TRIE::Sf(0))!=-1)TRIE::upd(to,0),pr[to]=-1;
		
		
	}
	else 
	{
		for(auto to:v[x])
		{
			if(to==son[x])continue;
			all.clear(),get(to);
			for(auto it:all)lin[to].push_back({it,pr[it]}),tdis-=it-1-pr[it],pr[it]=-1,TRIE::upd(it,0);
		}
		if(ed[x])
		{
			int it=ed[x];
			tdis-=it-1-pr[it],pr[it]=-1,TRIE::upd(it,0);
		}
		solve(son[x],len);
		for(auto to:v[x])
		{
			if(to==son[x])continue;
			for(auto [x,y]:lin[to])pr[x]=y,tdis+=x-1-pr[x],TRIE::upd(x,1);
			for(auto [x,y]:lin[to])
			{
				int ty=TRIE::Pr(pr[x]);
				if(ty!=-1)q.push({pr[x]-ty+1,x});
			}
			
			vector<array<int,2> >().swap(lin[to]);
			solve(to,len);
		}
	}
//	for(int i=0;i<=n;i++)cerr<<i<<" "<<pr[i]<<"AAA\n";
}

char ED;
int main(){
	cerr<<abs(&ST-&ED)/1024./1024<<"\n";
//	freopen("a.in","r",stdin);
	//进入新子树之前重新清空，一个节点只会有一个 end。 
	TRIE::cls(2e5+5);
	int T=read();
	while(T--)
	{
		for(int i=1;i<=cst;i++)e[i]=e[0],ed[i]=0,v[i].clear(),lin[i].clear();
		lst=cst=1;ans=0;
		scanf("%s",s+1);
		n=strlen(s+1);
		for(int i=0;i<=n;i++)pr[i]=-1;
		for(int i=n;i>=1;i--)add(s[i]-'a'),ed[lst]=i;
		
		for(int i=2;i<=cst;i++)v[e[i].link].push_back(i);//,cerr<<i<<" "<<e[i].link<<"%%%%%%^%^\n";
		dfs(1,0);
//		cerr<<cst<<"$\n";
		
		for(auto to:v[1])
		{
			all.clear(),get(to);
			for(auto id:all)pr[id]=id,tdis--,q.push({1,id}),TRIE::upd(id,1);
//			cerr<<siz(q)<<" "<<ed[2]<<" "<<ed[3]<<" "<<siz(all)<<"$\n";
			//急了，应该从小到大相等时，他是非严格前驱。 
			
			solve(to,0);
//			cerr<<"_____________\n";
//	for(int i=0;i<=n;i++)cerr<<i<<" "<<pr[i]<<"#\n";
			
		}
		
		cout<<ans<<"\n";
	}
	
	pc('1',1);
	return 0;
}

}signed main(){return ifzw::main();}