#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define md(a) a=(a%mod+mod)%mod
#define file(a) freopen(#a".in","r",stdin);freopen(#a".out","w",stdout)

bool ST;

const int N=200005,P1=131,mod1=998244353,P2=13331,mod2=36634229,M=19491001;
int n,p1[N],p2[N],h1[N],h2[N],st[N],top;char s[N];

struct Tree
{
	struct SAM{int c[26],fa,len;}t[N*2];int tot;
	inline int New(int len){tot++;for(int i=0;i<26;i++)t[tot].c[i]=0;t[tot].fa=0,t[tot].len=len;return tot;}
	inline void Build(){tot=-1;New(0);t[0].fa=-1;}
	inline void Copy(int x,int y){for(int i=0;i<26;i++)t[x].c[i]=t[y].c[i];t[x].fa=t[y].fa;}
	inline int ins(int p,int a)
	{
		int cur=New(t[p].len+1);while(p!=-1&&!t[p].c[a])t[p].c[a]=cur,p=t[p].fa;
		if(p==-1){t[cur].fa=0;return cur;}int q=t[p].c[a];if(t[p].len+1==t[q].len){t[cur].fa=q;return cur;}
		int cl=New(t[p].len+1);Copy(cl,q);while(p!=-1&&t[p].c[a]==q)t[p].c[a]=cl,p=t[p].fa;t[cur].fa=t[q].fa=cl;return cur;
	}
	inline ll Get(){ll ans=0;for(int i=1;i<=tot;i++)ans+=t[i].len-t[t[i].fa].len;return ans;}
}T;

inline int H1(int l,int r){if(l>r)return 0;int w=(h1[r]-1ll*h1[l-1]*p1[r-l+1])%mod1;if(w<0)w+=mod1;return w;}
inline int H2(int l,int r){if(l>r)return 0;int w=(h2[r]-1ll*h2[l-1]*p2[r-l+1])%mod2;if(w<0)w+=mod2;return w;}
inline bool check(int l1,int r1,int l2,int r2)
{
	if(H1(l1,r1)!=H1(l2,r2))return 0;
	if(H2(l1,r1)!=H2(l2,r2))return 0;
	return 1;
}
inline int lcp(int x,int y)
{
	int l=1,r=min(n-x+1,n-y+1),mid,ans=0;
	while(l<=r){mid=(l+r)>>1;if(check(x,x+mid-1,y,y+mid-1))ans=mid,l=mid+1;else r=mid-1;}
	return ans;
}
inline int lcs(int x,int y)
{
	int l=1,r=min(x,y),mid,ans=0;
	while(l<=r){mid=(l+r)>>1;if(check(x-mid+1,x,y-mid+1,y))ans=mid,l=mid+1;else r=mid-1;}
	return ans;
}

inline bool cmp(int x,int y)//suf[x]<suf[y]
{
	if(x==y)return 0;int p=n-x+1,q=n-y+1,ans=lcp(x,y);
	if(ans==p)return 1;if(ans==q)return 0;return s[x+ans]<s[y+ans];
}

struct Runs{int l,r,p;}p[N],np[N*2];int cnt,tot;
inline bool sml(Runs a,Runs 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;}

inline bool saf(Runs a){if(a.p*2>a.r-a.l+1)return 0;return 1;}

map<pair<int,int>,bool>mp;ll ans;
inline void check(int l,int r,int p)
{
	// cout<<"chk:"<<l<<' '<<r<<' '<<p<<'\n';
	for(int st=l;st<=l+p-1;st++)
	{
		for(int ed=st+p*2-1;ed<=r;ed+=p)
		{
			int h1=H1(st,ed),h2=H2(st,ed);
			if(!mp.count({h1,h2}))mp[{h1,h2}]=1,ans--;
		}
	}
}

inline void solve()
{
	cin>>(s+1),n=strlen(s+1);st[0]=n+1;cnt=tot=0;mp.clear();
	for(int i=1;i<=n;i++)h1[i]=(1ll*h1[i-1]*P1+s[i])%mod1,h2[i]=(1ll*h2[i-1]*P2+s[i])%mod2;
	for(int i=n;i>=1;i--)
	{
		while(top&&cmp(i,st[top]))top--;;int l=i,r=st[top]-1,f,g;st[++top]=i;
		f=lcs(l-1,r),g=lcp(l,r+1);np[++tot]={l-f,r+g,r-l+1};if(!saf(np[tot]))tot--;
	}top=0;
	for(int i=n;i>=1;i--)
	{
		while(top&&cmp(st[top],i))top--;;int l=i,r=st[top]-1,f,g;st[++top]=i;
		f=lcs(l-1,r),g=lcp(l,r+1);np[++tot]={l-f,r+g,r-l+1};if(!saf(np[tot]))tot--;
	}top=0;
	sort(np+1,np+tot+1,sml);
	for(int i=1;i<=tot;i++)
	{
		if(cnt&&p[cnt].l==np[i].l&&p[cnt].r==np[i].r)continue;
		if(i==1||sml(np[i-1],np[i]))p[++cnt]=np[i];
	}
	
	T.Build();for(int i=1,p=0;i<=n;i++)p=T.ins(p,s[i]-'a');ans=T.Get();
	// cout<<ans<<'\n';
	for(int i=1;i<=cnt;i++)check(p[i].l,p[i].r,p[i].p);cout<<ans<<'\n';
}

bool ED;

signed main()
{
	cerr<<(&ST-&ED)/1024.0/1024<<'\n';ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);


	p1[0]=p2[0]=1;for(int i=1;i<N;i++)p1[i]=1ll*p1[i-1]*P1%mod1,p2[i]=1ll*p2[i-1]*P2%mod2;
	int T;cin>>T;while(T--)solve();
	return 0;
}