#include<bits/stdc++.h>
#define Misaka namespace
#define Mikoto std
using Misaka Mikoto;
int read()
{
	int s=0;
	char ch=getchar();
	while(ch<'0'||ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
	return s;
}
const int mxn=4e5+5;
struct SA
{
    #define f(i,a,b) for(i=a;i<=b;i++)
    #define e(i,a,b) for(i=a;i>=b;i--)
    int sa[mxn],height[mxn];
    int cnt[mxn],rk[mxn];
    int preN;
    void S_sort(char s[],int l,int m)
    {
        int i,k,ct;
        f(i,1,l) cnt[height[i]=s[i]]++;
        f(i,2,m) cnt[i]+=cnt[i-1];
        e(i,l,1) sa[cnt[height[i]]--]=i;
        for(k=1;k<=l;k*=2)
        {
            ct=0;
            f(i,l-k+1,l) rk[++ct]=i;
            f(i,1,l)
                if(sa[i]>k)
                    rk[++ct]=sa[i]-k;
            f(i,1,m) cnt[i]=0;
            f(i,1,l) cnt[height[i]]++;
            f(i,2,m) cnt[i]+=cnt[i-1];
            e(i,l,1) sa[cnt[height[rk[i]]]--]=rk[i],rk[i]=0;
//            swap(height,rk);
			f(i,1,l) swap(height[i],rk[i]);
            height[sa[1]]=m=1;
            f(i,2,l)
                height[sa[i]]=m=m+!(rk[sa[i]]==rk[sa[i-1]]&&rk[sa[i]+k]==rk[sa[i-1]+k]);
            if(m==l) return;    
        }
    }
    void build(char s[],int l,int m)
    {
    	memset(cnt,0,preN);
    	memset(rk,0,preN);
    	memset(sa,0,preN);
    	memset(height,0,preN);
        S_sort(s,l,m);    
        int i,j,k;
        for(i=1;i<=l;i++)
            rk[sa[i]]=i;
        for(i=1,k=0;i<=l;i++)
        {
            if(rk[i]==1) k=0;
            else
            {
                k-=k>0;
                int j=sa[rk[i]-1];
                while(i+k<=l&&j+k<=l&&s[i+k]==s[j+k])
                    k++;
            }
            height[rk[i]]=k;
        }
        preN=max(l,m)+1<<2;
    }
};
struct LCP_SA
{
	struct Word_RMQ
	{
		#define w 32
		#define u unsigned
		#define be(x) ((x>>5)+1)
		#define bm mxn/w+5
		int *a;
		int ST[int(log2(bm)+1)][bm];
		int lg[bm];
		int l[bm],r[bm];
		struct node
		{
			u st[w+1];
			int *p;
			int ask(int l,int r)
			{
				return p[l+__builtin_ctz(st[r]>>l-1)];
			}
			void init(int *p_,int len)
			{
				p=p_;
				int i,top=0;
				int stack[w+1];
				for(i=1;i<=len;i++)
				{
					st[i]=st[i-1];
					while(top&&p[i]<p[stack[top]])
						st[i]-=1u<<stack[top--]-1;
					stack[++top]=i,st[i]+=1u<<i-1;
				}
			}
		}k[bm];
		void build(int A[],int n)
		{
			a=A;
			int i,j,cnt=0,mn;
			for(i=0;i<=n;i+=w)
				l[++cnt]=i,r[cnt]=min(n,i+w-1);
			l[1]=1;
			for(i=1;i<=cnt;i++)
			{
				k[i].init(a+l[i]-1,r[i]-l[i]+1);
				mn=INT_MAX;
				for(j=l[i];j<=r[i];j++)
					mn=min(mn,a[j]);
				ST[0][i]=mn;
			}
			for(j=1;(1<<j)<=cnt;j++)
				for(i=1;i+(1<<j)-1<=cnt;i++)
					ST[j][i]=min(ST[j-1][i],ST[j-1][i+(1<<(j-1))]);
			for(i=2;i<=cnt;i++)
				lg[i]=lg[i>>1]+1;
		}
		inline int STask(int L,int R)
		{
			if(L>R) return INT_MAX;
			int k=lg[R-L+1];
			return min(ST[k][L],ST[k][R-(1<<k)+1]);
		}
		inline int ask(int L,int R)
		{
			if(L>R) return INT_MAX;
			if(be(L)==be(R)) return k[be(L)].ask(L-l[be(L)]+1,R-l[be(L)]+1);
			return min({STask(be(L)+1,be(R)-1),ask(L,r[be(L)]),ask(l[be(R)],R)});
		}
	}ds;
	SA a;
	int L;
	void build(char s[],int l,int m)
	{
		a.build(s,l,m);
		ds.build(a.height,l);
	}
	inline int asklcp(int x,int y)
	{
		if(x==y) return L-x+1;
		x=a.rk[x],y=a.rk[y];
		if(x>y) swap(x,y);
		return ds.ask(x+1,y);
	}
	#undef w
}a,b;
char s[mxn];
int t[mxn];
struct node
{
	int l,r,p;
}res[mxn*20],ans[mxn*20];
using ull=unsigned long long;
using ll=long long;
ull pre[mxn],mul[mxn];
int n;
const ull up=23333333333333;
ull ask(int l,int r)
{
	return mul[n-r]*(pre[r]-pre[l-1]);
}
int main()
{
	int T=read();
	while(T--)
	{
		int n,i,j,k,cnt=0;
		scanf("%s",s+1),n=strlen(s+1);
		::n=n;
		a.build(s,n,'z');
		reverse(s+1,s+1+n);
		b.build(s,n,'z');
		reverse(s+1,s+1+n);
		for(i=mul[0]=1;i<=n;i++)
			mul[i]=mul[i-1]*up,pre[i]=pre[i-1]+mul[i]*s[i];
	//	cerr<<clock()<<endl;
		int ticnt=0;
		for(i=1;i<=n/2;i++)
		{
			int L=-1,R=-1;
			for(j=i;j+i<=n;j+=i)
			{
				j=max(j,R/i*i);
				while(j<=R) j+=i;
				int lcp,lcs;
				for(lcp=1;lcp<=i&&s[j+lcp-1]==s[j+i+lcp-1];lcp++);
				lcp--;
				for(lcs=1;lcs<i&&s[j-1-lcs+1]==s[j+i-1-lcs+1];lcs++);
				lcs--;
				ticnt+=lcp+lcs;
				//[i-lcs,i+lcp-1]
				int l=j-lcs,r=j+lcp-1;
				if(L==-1) L=l,R=r;
				else if(l<=R+1)
					R=r;
				else 
				{
					if(R-L+1>=i)
						res[++cnt]=node({L,R+i,i});
					L=l,R=r;
				}
			}
			if(L!=-1&&R-L+1>=i)
				res[++cnt]=node({L,R+i,i});
			if(ticnt>n*100) break;
		}
	//	cerr<<i<<' '<<clock()<<endl;
	//	cerr<<clock()<<endl;
		for(;i<=n/2;i++)
		{
			int L=-1,R=-1;
			for(j=i;j+i<=n;j+=i)
			{
				j=max(j,R/i*i);
				while(j<=R) j+=i;
				int lcp=a.asklcp(j,j+i);
				int lcs=b.asklcp(n-(j-1)+1,n-(j+i-1)+1);
				//[i-lcs,i+lcp-1]
				int l=j-lcs,r=j+lcp-1;
				if(L==-1) L=l,R=r;
				else if(l<=R+1)
					R=r;
				else 
				{
					if(R-L+1>=i)
						res[++cnt]=node({L,R+i,i});
					L=l,R=r;
				}
			}
			if(L!=-1&&R-L+1>=i)
				res[++cnt]=node({L,R+i,i});
		}
		for(i=1;i<=cnt;i++)
			t[res[i].r]++;
		for(i=1;i<=n;i++)
			t[i]+=t[i-1];
		for(i=cnt;i;i--)
			ans[t[res[i].r]--]=res[i];
		memset(t,0,n+1<<2);
		for(i=1;i<=cnt;i++)
			t[ans[i].l]++;
		for(i=1;i<=n;i++)
			t[i]+=t[i-1];
		for(i=cnt;i;i--)
			res[t[ans[i].l]--]=ans[i];
		memset(t,0,n+1<<2);
		int acnt=0;
		for(i=1;i<=cnt;i=j)
		{
			int mn=2e9;
			for(j=i;j<=n&&res[j].l==res[i].l&&res[j].r==res[i].r;j++)
				mn=min(mn,res[j].p);
			ans[++acnt]=node({res[i].l,res[i].r,mn});
		}
		unordered_set<ull> st;
		ll s=1ll*n*(n+1)/2;
		for(i=2;i<=n;i++)
			s-=a.a.height[i];
//		cout<<s<<endl;
//		for(i=1;i<=acnt;i++)
//			cout<<ans[i].l<<' '<<ans[i].r<<' '<<ans[i].p<<endl;
		for(i=1;i<=acnt;i++)
			for(j=ans[i].l;j<=ans[i].l+ans[i].p;j++)	
				for(k=j+ans[i].p*2-1;k<=ans[i].r;k+=ans[i].p)
					st.insert(ask(j,k));
		printf("%lld\n",s-st.size());
	}
//	freopen("out","w",stdout);
}