可以知道，对于某$AB$，若其前缀$A'B',$其$|A'B'|\bigg ||AB|$,则其循环总长$|(AB)^n|\leq|(A'B')^{n'}|$，所以我们每次枚举循环节数可以利用上次的循环节数，例如对于$ababab$,$ab$的循环总长为$6$,而$abab$的循环总长为$4$

可以达到$\frac{1}{3}$甚至更低的常数

详见代码:

#include<map>
#include<set>
#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
# define ll long long
# define read read1<ll>()
# define Type template<typename T>
# define fre(k) freopen(k".in","r",stdin);freopen(k".out","w",stdout)
Type T read1(){
	T t=0;
	char k;
	bool vis=0;
	do (k=getchar())=='-'&&(vis=1);while('0'>k||k>'9');
	while('0'<=k&&k<='9')t=(t<<3)+(t<<1)+(k^'0'),k=getchar();
	return vis?-t:t;
}
# define ull unsigned ll
# define P1 998244353
# define P2 998244373
# define P3 1000000007
ull Hs[1048580][3],p[1048580][3];
int s,a[1048580],la[1048580],va[1048580];
bool vis[26],wh[26];
char str[1048580];
bool judge(int x,int l,int r){
	return (Hs[x][0]*p[l-1][0]==Hs[r][0]-Hs[l-1][0])&&(Hs[x][1]*p[l-1][1]==Hs[r][1]-Hs[l-1][1])&&(Hs[x][2]*p[l-1][2]==Hs[r][2]-Hs[l-1][2]);
}
void add(int x){++x;while(x<=27)++a[x],x+=x&-x;}
int que(int x){++x;int t=0;while(x)t+=a[x],x&=x-1;return t;}
int main(){
	//fre("string");
	p[0][0]=p[0][1]=p[0][2]=1;
	for(int i=1;i<=1048576;++i){
		p[i][0]=p[i-1][0]*P1;
		p[i][1]=p[i-1][1]*P2;
		p[i][2]=p[i-1][2]*P3;
	}
	for(int i=2;i*i<=1048576;++i){
		for(int j=i;j*i<=1048576;++j)
			if(!la[j*i])la[j*i]=j;
	}
	for(int T=read;T--;){
		int cnt=0,ch=0,tn=0;
		scanf("%s",str+1);
		s=strlen(str+1);
		memset(a,0,sizeof(a));
		memset(vis,0,sizeof(vis));
		memset(wh,0,sizeof(wh));
		for(int i=1;i<=s;++i){
			wh[str[i]-='a']^=1;
			Hs[i][0]=Hs[i-1][0]+str[i]*p[i-1][0];
			Hs[i][1]=Hs[i-1][1]+str[i]*p[i-1][1];
			Hs[i][2]=Hs[i-1][2]+str[i]*p[i-1][2];
		}
		for(int i=0;i<26;++i)cnt+=wh[i];
		ll ans=0;
		for(int i=1;i<s;++i){
			if(vis[str[i]]^=1)
				++ch;
			else --ch;
			if(wh[str[i]]^=1)++tn;
			else --tn;
			int f[2];
			f[1]=que(cnt+tn);
			f[0]=que(cnt);
			int tot=la[i]?va[la[i]]/(i/la[i]):0;
			if(i!=1)
				for(int j=1+tot*i;j+i<s+1;j+=i)
					if(judge(i,j,j+i-1))++tot;
					else break;
			add(ch);va[i]=tot;
			ans+=1ll*(tot+1>>1)*f[1];
			ans+=1ll*(tot>>1)*f[0];
		}
		printf("%lld\n",ans);
	}
	return 0;
}