#include<bits/stdc++.h>
using namespace std;
#define int long long
const int base=131;
int t,n,f[(1ll<<20)+5],hs[(1ll<<20)+5],pw[(1ll<<20)+5];
string s;
bool vis[(1ll<<20)+5];
struct BIT{
	int t[(1ll<<20)+5];
	void update(int cur,int val){
		cur++;
		for(int i=cur; i<=n+1; i+=(i&-i)) t[i]+=val;
		return;
	}
	int query(int cur){
		cur++;
		int sum=0;
		for(int i=cur; i; i-=(i&-i)) sum+=t[i];
		return sum;
	}
}T;
int help(int l,int r){return hs[r]-hs[l-1]*pw[r-l+1];}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	pw[0]=1;
	for(int i=1; i<=1000000; i++) pw[i]=pw[i-1]*base;
	cin>>t;
	while(t--){
		cin>>s;n=s.size(),s=" "+s;
		for(int i=1; i<=n; i++) hs[i]=hs[i-1]*base+s[i];
		for(int i=1; i<=n+1; i++) T.t[i]=0;
		for(int i='a'; i<='z'; i++) vis[i]=false;
		int sum=0,ans=0;
		for(int i=n; i>=1; i--){
			if(!vis[s[i]]) vis[s[i]]=true,sum++;
			else vis[s[i]]=false,sum--;
			f[i]=sum;
		}
		for(int i='a'; i<='z'; i++) vis[i]=false;
		sum=0;
		for(int i=1; i<=n; i++){
			if(!vis[s[i]]) vis[s[i]]=true,sum++;
			else vis[s[i]]=false,sum--;
			int nw=1;
			while(nw+i-1<n){
				if(help(1,i)!=help(nw,nw+i-1)) break;
				ans+=T.query(f[nw+i]);
				nw+=i;
			}
			T.update(sum,1);
		}
		cout<<ans<<'\n';
	}
	return 0;
}

思路就是暴力枚举循环节长度然后往后跳，用树状数组更新答案。

理论上是调和级数+树状数组的两只log，但是轻松过了，最慢的点只有700多ms