If we enumerate $C$and use the KMP algorithm to calculate the minimum loop section, the complexity $\Theta (Tn \sqrt n)$of the factor of the loop section length for each enumeration can be 84 points, which is sufficient for the NOIP first prize.

But the exact solution is not difficult either. We find that when enumerating factors, many enumerations are meaningless. We are considering a different approach. Enumeration $AB$, then enumerate the number of loops, and the remaining segment is $C$. For odd occurrences of characters, prefixes and techniques can be used to maintain them. The overall complexity is $\ Theta (n\ln n)$. The natural logarithm comes from harmonic series.

#include<bits/stdc++.h>
#define int long long
#define uint unsigned long long
using namespace std;
const int N=1048577,B=131;
int T,n,ans;
string s;
uint ha[N],fac[N];
int cnt[26],suf[N];
int pre_cnt[27];
inline int getha(int l,int r) {
	return ha[r]-ha[l-1]*fac[r-l+1];
}
signed main() {
	std::ios::sync_with_stdio(0),cin.tie(0);
	cin>>T;
	while(T--) {
		cin>>s;
		n=s.size();
		s=" "+s;
		fac[0]=1,ans=0;
		for(int i=1; i<=n; ++i) {
			fac[i]=fac[i-1]*B;
			ha[i]=ha[i-1]*B+s[i];
		}
		memset(cnt,0,sizeof cnt);
		for(int i=n,nw=0; i>=1; --i) {
			++cnt[s[i]-'a'];
			if(cnt[s[i]-'a']&1)++nw;
			else --nw;
			suf[i]=nw;
		}
		memset(cnt,0,sizeof cnt);
		memset(pre_cnt,0,sizeof pre_cnt);
		for(int i=1,nw=0; i<=n; ++i) {
			if(i>=2) {
				for(int j=1; j*i<n; ++j) {
					if(getha(1,i)==getha(1+(j-1)*i,j*i)) {
						ans+=pre_cnt[suf[j*i+1]];
					} else break;
				}
			}
			++cnt[s[i]-'a'];
			if(cnt[s[i]-'a']&1)++nw;
			else --nw;
			for(int j=0; j<=26; ++j) {
				if(j>=nw) ++pre_cnt[j];
			}
		}
		cout<<ans<<'\n';
	}
	return 0;
}