求卡常 悬一关

#include<bits/stdc++.h>
#define N 1200005
#define base 11451
#define lowbit(x) x&(-x)
#define int unsigned long long
using namespace std;
char a[N];
int ha[N];
int bk[N];
int tree[N];
string s;
void read()
{
	s="";
	char ch=getchar();
	while(ch<'a'||ch>'z')	ch=getchar();
	while(ch>='a'&&ch<='z')
	{
		s+=ch;
		ch=getchar();
	}
	return;
}
void add(int u,int v){
	while(u<=N){
		tree[u]+=v;
		u+=lowbit(u);
	}
	return;
}
int qu(int u){
	int sum=0;
	while(u){
		sum+=tree[u];
		u-=lowbit(u);
	}
	return sum;
}
int suan(int l,int r){
	return ha[r]-ha[l-1]*bk[r-l+1];
}
int cnt[30];
int match[N];
vector<int> vec[N];
vector<int> v1[N];
void write(int x)
{
	if(x>9)	write(x/10);
	putchar(x%10+'0');
}
signed main(){
	//freopen("P7114_23.in","r",stdin);
	//freopen("string.out","w",stdout);
	bk[0]=1;
	for(int i=1;i<N;i++){
		bk[i]=bk[i-1]*base;
	}
	int t;
	scanf("%d",&t);
	while(t--){
		//ch=0;
		read();
		int l=s.length();
		ha[0]=0;
		ha[l+1]=0;
		for(int i=1;i<=l;i++){
			//ch++;
			ha[i]=ha[i-1]*base;
			ha[i]+=s[i-1]-'a'+1;
		}
		int cntj=0;
		for(int i=1;i<=27;i++){
			//ch++;
			cnt[i]=0;
		}
		for(int i=l;i>=1;i--){
			//ch++;
			cnt[s[i-1]-'a'+1]++;
			if(cnt[s[i-1]-'a'+1]%2==1)cntj++;
			else cntj--;
			match[i-1]=cntj;
		}
		//cout<<"l:"<<l<<endl;
		for(int i=1;i<=l;i++){
			int ans1=suan(1,i);
			for(int j=1;j+i-1<=l;j+=i){
				if(j+i-1==l)continue;
				//ch++;
				if(suan(j,j+i-1)!=ans1){
					break;
				}
				//cout<<"i:"<<i<<" "<<j<<" "<<match[j+i-1]<<endl;
				vec[i].push_back(match[j+i-1]); 
			}
		}
		for(int i=1;i<=27;i++){
			cnt[i]=0;
		}
		cntj=0;
		for(int i=1;i<=l;i++){
			//ch++;
			cnt[s[i-1]-'a'+1]++;
			if(cnt[s[i-1]-'a'+1]%2==1)cntj++;
			else cntj--;
			//cout<<"::"<<i+1<<" "<<cntj<<endl; 
			v1[i+1].push_back(cntj);
		}
		int ans=0;
		int cnt0=0;
		int ssum=0;
		for(int i=l;i>=1;i--){
			for(int j=0;j<vec[i].size();j++){
				int k=vec[i][j];
				if(k!=0){
					ssum++;
					add(k,1);
				}
				else
				cnt0++;
			}
			for(int j=0;j<v1[i].size();j++){
				int k=v1[i][j];
				if(k!=0){
				//	cout<<i<<" "<<v1[i][j]<<endl;
				//	cout<<qu(N)-qu(k-1)<<endl;
					ans+=ssum-qu(k-1);
				}
				else{
				//	cout<<i<<" "<<v1[i][j]<<endl;
				//	cout<<qu(N)+cnt0<<endl;
					ans+=ssum+cnt0;
				}
			}
		}
		for(int i=l;i>=1;i--){
			for(int j=0;j<vec[i].size();j++){
				int k=vec[i][j];
				if(k!=0)
				add(k,-1);
			}
		}
		for(int i=0;i<=l+2;i++){
			vec[i].clear();
			v1[i].clear();
		}
		write(ans);
		putchar('\n');
	}
	return 0;
}