我好慌啊

//I am hunting for the golden stag.
#include <cstring>
#include <cstdio>
typedef long long ll;
const int maxn = 2e6 + 10;
const int base = 131;
const int mod = 1e9 + 7;
int t,pre[maxn],suf[maxn],sum[maxn][27],cnt[27],power[maxn] = { 1 };
ll ash[maxn];
char str[maxn];
inline ll sub(int l,int r) {
	return (ash[r]-ash[l-1]*power[r-l+1]%mod+mod)%mod;
}
int main() {
	for (int i = 1;i < maxn;i++) power[i] = 1ll*power[i-1]*base%mod;
	for (scanf("%d",&t);t--;) {
		scanf("%s",str+1);
		int n = strlen(str+1);
		for (int i = 1;i <= n;i++) {
			ash[i] = suf[i] = pre[i] = 0;
			for (int j = 0;j <= 26;j++) sum[i][j] = 0;
		}
		memset(cnt,0,sizeof cnt);
		for (int i = 1;i <= n;i++) {
			cnt[str[i]-'a']++;
			pre[i] = pre[i-1];
			if (!(cnt[str[i]-'a']&1)) pre[i]--;
			else pre[i]++;
		}
		memset(cnt,0,sizeof cnt);
		for (int i = n;i >= 1;i--) {
			cnt[str[i]-'a']++;
			suf[i] = suf[i+1];
			if (!(cnt[str[i]-'a']&1)) suf[i]--;
			else suf[i]++;
		}
		for (int i = 1;i <= n;i++)
			for (int j = 0;j <= 26;j++) {
				sum[i][j] = sum[i-1][j];
				if (pre[i] <= j) sum[i][j]++;
			}
		for (int i = 1;i <= n;i++) ash[i] = (ash[i-1]*base+str[i])%mod;
		ll ans = 0;
		for (int i = 2;i <= n;i++)
			for (int now = 1;now+i <= n;now += i) {
				if (sub(now,now+i-1) ^ ash[i]) break;
				//for (int j = 1;j < i;j++) if (pre[j] <= suf[now+i]) ans++;
				ans += sum[i-1][suf[now+i]];
			}
		printf("%lld\n",ans);
	}
	return 0;
}