#include<bits/stdc++.h>
using namespace std;
const int N=60005,Z=26;
int n,lg[N<<1],pw[20];
typedef long long ll;
struct SAM
{
	int ch[N][26],len[N],fa[N],tot,rt,las,pos[N];
	inline int nd()
	{
		int p=++tot;memset(ch[p],0,sizeof ch[p]);
		len[p]=fa[p]=0;return p;
	}
	inline void pre(){tot=0;rt=las=nd();}
	inline void extend(int c,int now)
	{
		int np=nd(),p=las;las=np;
		len[np]=len[p]+1;pos[now]=np;
		for(;p&&!ch[p][c];p=fa[p])ch[p][c]=np;
		if(!p){fa[np]=rt;return;}
		int q=ch[p][c];
		if(len[q]==len[p]+1){fa[np]=q;return;}
		int nq=nd();len[nq]=len[p]+1;fa[nq]=fa[q];
		for(int i=0;i<Z;++i)ch[nq][i]=ch[q][i];
		fa[q]=fa[np]=nq;
		for(;p&&ch[p][c]==q;p=fa[p])ch[p][c]=nq;
	}
	int cnt,fi[N],ne[N],to[N],dep[N],op[N<<1],tim,st[N<<1][20],id[N];
	inline void add(int x,int y){ne[++cnt]=fi[x],fi[x]=cnt,to[cnt]=y;}
	inline void build(){for(int i=2;i<=tot;++i)add(fa[i],i);}
	void dfs(int u)
	{
		op[++tim]=u;id[u]=tim;
		for(int i=fi[u];i;i=ne[i])
		{
			int v=to[i];
			dep[v]=dep[u]+1;dfs(v);
			op[++tim]=u;
		}
	}
	inline int Min(int x,int y){return dep[x]<dep[y]?x:y;}
	inline void ST()
	{
		for(int i=1;i<=tim;++i)st[i][0]=op[i];
		for(int i=1;i<=lg[tim];++i)
			for(int j=1;j+pw[i]-1<=tim;++j)
				st[j][i]=Min(st[j][i-1],st[j+pw[i-1]][i-1]);
	}
	inline int lca(int x,int y)
	{
		x=id[x],y=id[y];
		if(x>y)swap(x,y);
		int len=lg[y-x+1];
		return Min(st[x][len],st[y-pw[len]+1][len]);
	}
	inline int query(int x,int y){return len[lca(pos[x],pos[y])];}
	inline void clear(){cnt=0;fill(fi+1,fi+tot+1,0);tim=0;}
}A,B;
char s[N];int a[N],b[N];
inline void upd(bool tp,int l,int r)
{
	if(l>r)return;
	if(!tp)++a[l],--a[r+1];
	else ++b[l],--b[r+1];
}
int main()
{
	int T,bbl=120000;scanf("%d",&T);
	lg[1]=0;for(int i=2;i<=bbl;++i)lg[i]=lg[i>>1]+1;
	pw[0]=1;for(int i=1;i<=lg[bbl];++i)pw[i]=pw[i-1]<<1;
	while(T--)
	{
		scanf("%s",s+1);
		n=strlen(s+1);A.pre(),B.pre();
		for(int i=1;i<=n;++i)A.extend(s[i]-'a',i);
		for(int i=n;i;--i)
		B.extend(s[i]-'a',i);
		A.build(),B.build();
		A.dfs(A.rt),B.dfs(B.rt);
		A.ST(),B.ST();
		for(int i=1;i<=n/2;++i)
			for(int j=i;j+i<=n;j+=i)
			{
				int lcs=min(A.query(j,j+i),i);
				int lcp=min(B.query(j,j+i),i);
				if(lcs+lcp<i)continue;
				upd(0,max(j-lcs+2*i,1),min(j+i+lcp-1,n));
				upd(1,max(j-lcs+1,1),min(j+i+lcp-2*i,n));
			}
		ll ans=0;
		for(int i=1;i<=n;++i)a[i]+=a[i-1],b[i]+=b[i-1];
		for(int i=2;i<n;++i)ans+=1ll*a[i]*b[i+1];
		printf("%lld\n",ans);
		fill(a+1,a+n+2,0);fill(b+1,b+n+2,0);
		A.clear(),B.clear();
	}
	return 0;
}