#include <bits/stdc++.h>
using namespace std;
#define il inline
#define ll long long

const int N=3e4+5,K=15;

int T,n;
int a[N],b[N];
char s[N];
struct SufAry{
	int m,o;
	int sa[N],t[N],x[N],y[N],rk[N],ht[N],mn[N][K];
	char str[N];
	il void SA(){
		m=122;
		for(int i=1;i<=m;++i)t[i]=0;
		for(int i=1;i<=n;++i)++t[x[i]=str[i]];
		for(int i=1;i<=m;++i)t[i]+=t[i-1];
		for(int i=n;i;--i)sa[t[x[i]]--]=i;
		for(int k=1;k<=n;k<<=1){
			int num=0;
			for(int i=n-k+1;i<=n;++i)y[++num]=i;
			for(int i=1;i<=n;++i){
				if(sa[i]>k)y[++num]=sa[i]-k;
			}
			for(int i=1;i<=m;++i)t[i]=0;
			for(int i=1;i<=n;++i)++t[x[y[i]]];
			for(int i=1;i<=m;++i)t[i]+=t[i-1];
			for(int i=n;i;--i)sa[t[x[y[i]]]--]=y[i];
			swap(x,y);
			x[sa[1]]=num=1;
			for(int i=2;i<=n;++i)x[sa[i]]=(sa[i-1]+k<=n&&y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])?num:++num;
			if(num>=n)break;
			m=num;
		}
		return ;
	}
	il void Height(){
		int k=0;
		for(int i=1;i<=n;++i)rk[sa[i]]=i;
		for(int i=1;i<=n;++i){
			if(rk[i]==1)continue;
			k?--k:0;
			int j=sa[rk[i]-1];
			while(i+k<=n&&j+k<=n&&str[i+k]==str[j+k])++k;
			ht[rk[i]]=k;
		}
		return ;
	}
	il void ST(){
		for(int i=1;i<=n;i++)mn[i][0]=ht[i];
		int l=__lg(n-1);
		for(int j=1;j<=l;j++){
			for(int i=1;i+(1<<j)-1<=n;i++)mn[i][j]=min(mn[i][j-1],mn[i+(1<<(j-1))][j-1]);
		}
		return ;
	}
	il int Min(int x,int y){
		o?(x=rk[n+1-x],y=rk[n+1-y]):(x=rk[x],y=rk[y]);
		x>y?swap(x,y):void(0);
		int l=__lg(y-x);
		return min(mn[x+1][l],mn[y-(1<<l)+1][l]);
	}
	il void Build(int opt){
		for(int i=1;i<=n;i++)str[i]=s[i];
		(o=opt)?reverse(str+1,str+1+n):void(0);
		SA(),Height(),ST();
		return ;
	}
}lcp,lcs;

il void Build(){
	cin>>(s+1);
	n=strlen(s+1);
	lcp.Build(1),lcs.Build(0);
	fill(a+1,a+1+n,0),fill(b+1,b+1+n,0);
	for(int len=1;len<n/2;++len){
		for(int i=len,j=i+len;j<=n;i+=len,j+=len){
			if(s[i]!=s[j])continue;
			int pre=lcp.Min(i,j),suf=lcs.Min(i,j);
			if(pre+suf<=len)continue;
			int La=i+1-min(pre,len),Ra=i+1+min(0,suf-len),Lb=La+(len<<1)-1,Rb=Ra+(len<<1)-1;
			++a[La],--a[Ra],++b[Lb],--b[Rb];
		}
	}
	for(int i=1;i<=n;i++)a[i]+=a[i-1],b[i]+=b[i-1];
	ll ans=0;
	for(int i=1;i<n;i++)ans+=(ll)b[i]*a[i+1];
	cout<<ans<<"\n";
	return ;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>T;
	while(T--)Build();
	return 0;
}