#include <bits/stdc++.h>

#define int long long

using namespace std;

const int MAXN=(1<<20)+17;

int n, a[MAXN], suf[MAXN], pre[MAXN][30], nxt[MAXN], f[MAXN], ans;
char s[MAXN];

void run()
{
	memset(f, 0, sizeof f), memset(suf, 0, sizeof suf), memset(pre, 0, sizeof pre), ans=0;
	for(int i=0; i<=n; i++) fill(pre[i], pre[i]+30, 0);
	scanf("%s", s+1), n=strlen(s+1);
	for(int i=1; i<=n; i++) a[i]=s[i]-'a';
	int odd=0, cnt=0;
	for(int i=n; i>=1; --i){
		odd&(1<<a[i])?--cnt:++cnt;
		odd^=1<<a[i], suf[i]=cnt;
	} odd=cnt=0;
	for(int i=1; i<=n; i++){
		odd&(1<<a[i])?--cnt:++cnt;
		odd^=1<<a[i];
		for(int j=0; j<=26; ++j) pre[i][j]=pre[i-1][j]+(j>=cnt);
	}
	for(int i=2, j=0; i<=n; i++){
		while(j && s[j+1]!=s[i]) j=nxt[j];
		if(s[j+1]==s[i]) nxt[i]=++j;
		if(j && i%(i-j)==0) f[i-j]=i;
	}
//	cout<<"f[i]:"; for(int i=1; i<=n; i++) cout<<f[i]<<' '; cout<<endl;
//	cout<<"suf[i]:"; for(int i=1; i<=n+1; i++) cout<<suf[i]<<' '; cout<<endl;
	for(int i=2; i<n; i++)
		if(f[i] || nxt[i] && i%(i-nxt[i])==0 && f[i-nxt[i]]){
			int tmp=(f[i]?f[i]:f[i-nxt[i]])/i;
//			cout<<i<<' '<<tmp<<' '<<pre[i-1][suf[i*2+1]]<<' '<<pre[i-1][suf[i+1]];
			int tt=ans;
			ans+=(tmp+1)/2*pre[i-1][suf[i+1]];
			if(i*2+1<=n) ans+=tmp/2*pre[i-1][suf[i*2+1]];
//			cout<<' '<<ans-tt<<endl;
		}
		else ans+=pre[i-1][suf[i+1]];
	cout<<ans<<endl;
}

signed main()
{
	int T; cin>>T;
	while(T--) run();
	return 0;
}