#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define N 33333
#define mod 30000010
char s[N];
LL hs[N],bs[N],u[N],v[N],ans;
LL gethash(int l,int r){
	return ((hs[l]-hs[r]*bs[r-l])%mod+mod)%mod;
}
signed main(){
	int T;scanf("%d",&T);
	bs[0]=1;
	for (int i=1;i<N;++i) bs[i]=bs[i-1]*27%mod;
	while (T --> 0){
		scanf("%s",s+1);
		int n=strlen(s+1);		
		memset(u,0,sizeof(u));
		memset(v,0,sizeof(v));
		hs[n+1]=0;
		for (int i=n;i;--i){
			hs[i]=(hs[i+1]*27+s[i]-'a'+1)%mod;
		}
		for (int j=1;j*2<=n;++j){
			for (int i=j*2;i<=n;i+=j){
				if (s[i]!=s[i-j]) continue;
				int l=1,r=j,lst=i-j,pos=0;
				while (l<=r){
					int mid=(l+r)/2;
					if (gethash(lst-mid+1,lst+1)==gethash(i-mid+1,i+1)){
						pos=mid;l=mid+1;
					}else r=mid-1;
				}
				int t=i-pos+1;
				l=1,r=j,pos=0;
				while (l<=r){
					int mid=(l+r)/2;
					if (gethash(lst,lst+mid)==gethash(i,i+mid)){
						pos=mid;l=mid+1;
					}else r=mid-1;
				}
				int w=i+pos-1;
				t=max(t+j-1,i);
				w=min(w,i+j-1);
				if (t<=w){
					u[t-2*j+1]++;u[w-2*j+2]--;
					v[t]++;v[w+1]--;
				}
			}
		}
		ans=0;
		for (int i=1;i<=n;++i){
			u[i]+=u[i-1];
			v[i]+=v[i-1];
		} 
		for (int i=1;i<n;++i) ans+=v[i]*u[i+1];
		printf("%lld\n",ans);
	}
	return 0;
}