如题

#include<bits/stdc++.h>
using namespace std;
const int N=1100000;
char s[N];
unsigned int cnt[N];
unsigned int cnt2[27][N];
unsigned int nxt[N];
unsigned int n,ddd;
unsigned int h[N],e[15000000],ne[15000000],idx;
inline void work(){
	scanf("%s",s+1);n=strlen(s+1);
	for(unsigned int i=2;i<=n;++i){
		unsigned int j=nxt[i-1];
		while(j&&s[j+1]!=s[i])	j=nxt[j];
		if(s[j+1]==s[i])	nxt[i]=j+1;
		else    nxt[i]=0;
	}
	for(unsigned int i=1;i<=n;++i){
		cnt[i]=cnt[i-1]^(1u<<(s[i]-'a'));
		unsigned int tmp=__builtin_popcount(cnt[i]);
		cnt2[0][i]=cnt2[0][i-1];
		cnt2[1][i]=cnt2[1][i-1];
		cnt2[2][i]=cnt2[2][i-1];
		cnt2[3][i]=cnt2[3][i-1];
		cnt2[4][i]=cnt2[4][i-1];
		cnt2[5][i]=cnt2[5][i-1];
		cnt2[6][i]=cnt2[6][i-1];
		cnt2[7][i]=cnt2[7][i-1];
		cnt2[8][i]=cnt2[8][i-1];
		cnt2[9][i]=cnt2[9][i-1];
		cnt2[10][i]=cnt2[10][i-1];
		cnt2[11][i]=cnt2[11][i-1];
		cnt2[12][i]=cnt2[12][i-1];
		cnt2[13][i]=cnt2[13][i-1];
		cnt2[14][i]=cnt2[14][i-1];
		cnt2[15][i]=cnt2[15][i-1];
		cnt2[16][i]=cnt2[16][i-1];
		cnt2[17][i]=cnt2[17][i-1];
		cnt2[18][i]=cnt2[18][i-1];
		cnt2[19][i]=cnt2[19][i-1];
		cnt2[20][i]=cnt2[20][i-1];
		cnt2[21][i]=cnt2[21][i-1];
		cnt2[22][i]=cnt2[22][i-1];
		cnt2[23][i]=cnt2[23][i-1];
		cnt2[24][i]=cnt2[24][i-1];
		cnt2[25][i]=cnt2[25][i-1];
		cnt2[26][i]=cnt2[26][i-1];
		for(unsigned int j=tmp;j<=26;++j)	cnt2[j][i]=cnt2[j][i-1]+1;
	}
	unsigned long long ans=0;
	for(unsigned int pl=3;pl<=n;++pl){
		unsigned int h1=pl-1-nxt[pl-1];
		unsigned int tmp=__builtin_popcount(cnt[n]^cnt[pl-1]);
		if((pl-1)%h1){
			ans+=cnt2[tmp][pl-2];
		}
		else{
			for(unsigned int i=h[(pl-1)/h1];i;i=ne[i]){
				ans+=cnt2[tmp][e[i]*h1-1];
			}
		}
	}
	printf("%lld\n",ans);
	return;
}
int main(){
	for(unsigned int i=1;i<=(1<<20);++i){
		for(unsigned int j=i;j<=(1<<20);j+=i){
			e[++idx]=i;ne[idx]=h[j];h[j]=idx;
			ddd++;
		}
	}
	unsigned int T;scanf("%d",&T);
	while(T--)	work();
	return 0;
}