#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<random>
#include<algorithm>
#define N 200000
#define Base1 131
#define Base2 171
#define mod1 998244853
#define mod2 993244853
using namespace std;
const int inf=(int)(1e9);
mt19937 RAND(random_device{}());
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 MD1(int x)
{
	return x>=mod1?x-mod1:x;
}
int MD2(int x)
{
	return x>=mod2?x-mod2:x;
}
int MD3(int x)
{
	return x<0?x+mod1:x;
}
int MD4(int x)
{
	return x<0?x+mod2:x;
}
struct reads
{
	int hsh1,hsh2;
	bool operator == (const reads &t)const
	{
		return hsh1==t.hsh1&&hsh2==t.hsh2;	
	}
};
reads rd[27],pw[N+1],hsh[N+1];
reads operator + (reads a,reads b)
{
	return (reads){MD1(a.hsh1+b.hsh1),MD2(a.hsh2+b.hsh2)};
}
reads operator - (reads a,reads b)
{
	return (reads){MD3(a.hsh1-b.hsh1),MD4(a.hsh2-b.hsh2)};
}
reads operator * (reads a,reads b)
{
	return (reads){1ll*a.hsh1*b.hsh1%mod1,1ll*a.hsh2*b.hsh2%mod2};
}
reads F(int l,int r)
{
	return hsh[r]-hsh[l-1]*pw[r-l+1];
}
int T,n,Base,Baset,length,st[N+1],leng,tmp[N+1],pv[N+1],sa[N+1],rk[N+1],cnt[N+1],scnt[N+1],num[N+1],h[N+1],delta[N+1];
long long S[N+1],res,ans;
char c[N+1],cs[N+1];
bool vis[N+1];
vector<int>p[N+1];
vector<int>v[N+1];
void build_SA()
{
	for (int i=1;i<=26;++i) cnt[i]=0;
	for (int i=1;i<=n;++i) num[i]=++cnt[cs[i]-'a'+1];
	for (int i=1;i<=26;++i) scnt[i]=scnt[i-1]+(cnt[i]>0),cnt[i]+=cnt[i-1];
	for (int i=1;i<=n;++i) sa[cnt[cs[i]-'a']+num[i]]=i,rk[i]=scnt[cs[i]-'a'+1];
	length=scnt[26];
	for (int i=1;i<=n&&length<n;i<<=1)
	{
		for (int j=1;j<=length;++j) cnt[j]=0;
		for (int j=n-i+1;j<=n;++j) num[j]=++cnt[rk[j]];
		for (int j=1;j<=n;++j)
			if (sa[j]>i)
				num[sa[j]-i]=++cnt[rk[sa[j]-i]];
		for (int j=2;j<=length;++j) cnt[j]+=cnt[j-1];
		for (int j=1;j<=n;++j) sa[cnt[rk[j]-1]+num[j]]=j;
		for (int j=1;j<=n;++j)
		{
			if (rk[sa[j]]!=rk[sa[j-1]]||((sa[j]+i<=n?rk[sa[j]+i]:0)!=(sa[j-1]+i<=n?rk[sa[j-1]+i]:0))) tmp[sa[j]]=tmp[sa[j-1]]+1;
			else tmp[sa[j]]=tmp[sa[j-1]];
		}
		for (int j=1;j<=n;++j) rk[j]=tmp[j];
		length=rk[sa[n]];
	}
	for (int i=1;i<=n;++i)
	{
		h[rk[i]]=max(h[rk[i-1]]-1,0);
		if (rk[i]!=1)
		{
			while (max(i,sa[rk[i]-1])+h[rk[i]]<=n&&cs[i+h[rk[i]]]==cs[sa[rk[i]-1]+h[rk[i]]]) h[rk[i]]++;
		}
	}
	return;
}
void finder(int x,int d,int sr)
{
	for (int i=0;i<p[x+1].size();++i)
		if (sr-d+1<=p[x+1][i]&&p[x+1][i]<=sr-Base-1)
			st[++leng]=p[x+1][i];
	return;
}
void del(vector<int>&sp)
{
	vector<int>st;
	for (int i=0;i<sp.size();++i)
		if (!vis[sp[i]])
			st.push_back(sp[i]);
	sp=st;
	return;
}
int main()
{
	int x,minn;
	string s;
	for (int i=1;i<=26;++i) rd[i]=(reads){(int)(RAND()%mod1),(int)(RAND()%mod2)};
	for (int i=1;i<=N;++i) S[i]=S[i-1]+i;
	T=read();
	while (T--)
	{
		cin>>s,n=s.length(),Base=sqrt(n),Baset=n/(Base+1),res=ans=0,pw[0]=(reads){1,1};
		for (int i=1;i<=n;++i) cs[n-i+1]=c[i]=s[i-1],hsh[i]=hsh[i-1]*(reads){Base1,Base2}+rd[c[i]-'a'+1],pw[i]=pw[i-1]*(reads){Base1,Base2},p[i].clear();
		build_SA();
		for (int i=1;i<=n;++i)
		{
			if (i!=1&&c[i]==c[i-1]) pv[i]=pv[i-1];
			else pv[i]=i;
		}
		for (int i=1;i<=n;++i)
		{
			leng=0;
			if (i-Base-1>=1)
			{
				x=rk[n-i+1],minn=inf;
				for (int j=x-1;j>=max(x-Baset,1)&&h[j+1]>=Base+1;--j)
				{
					minn=min(minn,h[j+1]);
					if (n-sa[j]+1<=i-Base-1) finder(n-sa[j]+1,minn,i);
				}
				minn=inf;
				for (int j=x+1;j<=min(x+Baset,n)&&h[j]>=Base+1;++j)
				{
					minn=min(minn,h[j]);
					if (n-sa[j]+1<=i-Base-1) finder(n-sa[j]+1,minn,i);
				}
			}
			for (int j=max(i-Base,1);j<=i-1;++j)
				if (delta[j]>=i-j+2&&F(delta[j]-(i-j+1),delta[j]-1)==F(j,i))
					st[++leng]=j;
			sort(st+1,st+leng+1);
			for (int j=1;j<=leng;++j) v[delta[st[j]]].push_back(st[j]);
			for (int j=1;j<=leng;++j)
				if (!v[delta[st[j]]].empty())
				{
					for (int k=0;k<v[delta[st[j]]].size();++k) vis[v[delta[st[j]]][k]]=1;
					del(p[delta[st[j]]]);
					for (int k=0;k<v[delta[st[j]]].size();++k) vis[v[delta[st[j]]][k]]=0;
					v[delta[st[j]]].clear();
				}
			for (int j=1;j<=leng;++j) pv[j]=delta[st[j]]-(i-st[j]+1);
			for (int j=1;j<=leng;++j) res+=delta[pv[j]]-delta[st[j]],delta[st[j]]=delta[pv[j]],p[delta[st[j]]].push_back(st[j]);
			res+=pv[i],delta[i]=pv[i],p[delta[i]].push_back(i),ans+=S[i]-res;
		}
		printf("%lld\n",ans);
	}
	return 0;
}