#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=4e5+5,p1=19491001,mod1=1e9+7,M=2e6+5,p2=131,mod2=998244353;
int T,n,pw1[N],h1[N],pw2[N],h2[N];
char s[N];
int hash1(int l,int r){return (h1[r]-(ll)h1[l-1]*pw1[r-l+1]%mod1+mod1)%mod1;}
int hash2(int l,int r){return (h2[r]-(ll)h2[l-1]*pw2[r-l+1]%mod2+mod2)%mod2;}
int lcp(int i,int j)
{
	int l=1,r=min(n-i+1,n-j+1),pos=0;
	while(l<=r)
	{
		int mid=l+r>>1;
		if(hash1(i,i+mid-1)==hash1(j,j+mid-1) && hash2(i,i+mid-1)==hash2(j,j+mid-1))pos=mid,l=mid+1;
		else r=mid-1;
	}
	return pos;
}
int lcs(int i,int j)
{
	int l=1,r=min(i,j),pos=0;
	while(l<=r)
	{
		int mid=l+r>>1;
		if(hash1(i-mid+1,i)==hash1(j-mid+1,j) && hash2(i-mid+1,i)==hash2(j-mid+1,j))pos=mid,l=mid+1;
		else r=mid-1;
	}
	return pos;
}
int cmp(int i,int j)
{
	int num=lcp(i,j);
	if(s[i+num]>s[j+num])return 1;
	if(s[i+num]==s[j+num])return 0;
	return -1;
}
int st[N],ct,top;
struct abc{int l,r,p;}runs[N];
bool cmp1(abc a,abc b){if(a.l!=b.l)return a.l<b.l;if(a.r!=b.r)return a.r<b.r;return a.p<b.p;}
void get_runs()
{
	ct=0,st[0]=n+1,top=0;
	for(int i=n;i>=1;i--)
	{
		while(top && cmp(i,st[top])<=0)top--;
		int l=i,r=st[top]-1,nl=l-lcs(l-1,r),nr=r+lcp(l,r+1);
		if(nr-nl+1>=(r-l+1)*2)ct++,runs[ct]=(abc){nl,nr,r-l+1};
		st[++top]=i;
	}
	top=0;
	for(int i=n;i>=1;i--)
	{
		while(top && cmp(i,st[top])>=0)top--;
		int l=i,r=st[top]-1,nl=l-lcs(l-1,r),nr=r+lcp(l,r+1);
		if(nr-nl+1>=(r-l+1)*2)ct++,runs[ct]=(abc){nl,nr,r-l+1};
		st[++top]=i;
	}
	sort(runs+1,runs+ct+1,cmp1);int ct1=0;
	for(int i=1;i<=ct;i++)if(runs[i].l!=runs[i-1].l || runs[i].r!=runs[i-1].r)ct1++,runs[ct1]=runs[i];
	ct=ct1;
}
// struct hash_table
// {
// 	const int K=4e5+5;
// 	int h[N],nxt[M],val[M],tot,clr[M],cv;
// 	void ins(int x)
// 	{
// 		int now=x%K;cv++,clr[cv]=now;
// 		for(int i=h[now];i;i=nxt[i])if(val[i]==x)return ;
// 		tot++,nxt[tot]=h[now],val[tot]=x,h[now]=tot;
// 	}
// 	void clr()
// 	{
// 		for(int i=1;i<=cv;i++)h[clr[i]]=0;
// 		tot=0,cv=0;
// 	}
// }t1;
map<pair<int,int>,int>t1;
struct SAM
{
	int tot;
	struct Tree{int ch[26],fa,len,sz;}t[N*4];
	void clr(){for(int i=0;i<=tot;i++){for(int j=0;j<26;j++)t[i].ch[j]=0;t[i].fa=t[i].len=0;}tot=0;}
	ll build()
	{
		int lst=0;
		for(int i=1;i<=n;i++)
		{
			// cout<<i<<endl;
			int now=++tot,p=lst,k=s[i]-'a';
			t[now].len=t[p].len+1,t[now].sz=1;
			while(1)
			{
				if(!t[p].ch[k])t[p].ch[k]=now;
				else
				{
					int q=t[p].ch[k];
					if(t[q].len==t[p].len+1)t[now].fa=q;
					else
					{
						int nq=++tot;
						t[nq]=t[q],t[nq].sz=0,t[nq].len=t[p].len+1,t[q].fa=t[now].fa=nq;
						while(t[p].ch[k]==q){t[p].ch[k]=nq;if(!p)break;p=t[p].fa;}
					}
					break;
				}
				if(!p)break;
				p=t[p].fa;
			}
			lst=now;
		}
		ll num=0;
		for(int i=1;i<=tot;i++)num+=t[i].len-t[t[i].fa].len;
		return num;
	}
}sam;
void solve()
{
	// scanf("%d",&n);
	scanf("%s",s+1);
	n=strlen(s+1);
	s[0]=s[n+1]='a'-1;
	for(int i=1;i<=n;i++)h1[i]=((ll)h1[i-1]*p1+s[i])%mod1;
	for(int i=1;i<=n;i++)h2[i]=((ll)h2[i-1]*p2+s[i])%mod2;
	get_runs(),t1.clear();
	for(int i=1;i<=ct;i++)
	{
		// cout<<runs[i].l<<" "<<runs[i].r<<" "<<runs[i].p<<endl;
		for(int j=runs[i].l;j<runs[i].l+runs[i].p;j++)
		{
			for(int k=j+2*runs[i].p-1;k<=runs[i].r;k+=runs[i].p)
			{
				t1[{hash1(j,k),hash2(j,k)}]=1;
			}
		}
	}
	sam.clr();
	ll res=sam.build();
	// cout<<res<<endl;
	res-=t1.size();
	printf("%lld\n",res);
}
int main()
{
	pw1[0]=1;for(int i=1;i<N;i++)pw1[i]=(ll)pw1[i-1]*p1%mod1;
	pw2[0]=1;for(int i=1;i<N;i++)pw2[i]=(ll)pw2[i-1]*p2%mod2;
	// freopen("book.in","r",stdin);
	// freopen("book.out","w",stdout);
	scanf("%d",&T);
	while(T--)solve();
	return 0;
}