我的思路是哈希+树状数组

#include<bits/stdc++.h>
#define int long long
#define N 2000006
#define mod1 998244353
#define mod2 1000000007 
#define base1 233333
#define base2 131
using namespace std;
int T, n, ans;
int pre[N], suf[N], vis[30];
int sum1[N], sum2[N], h1[N], h2[N];
string s;
int Get1(int L, int R) {
	return (sum1[R] - sum1[L - 1] * h1[R - L + 1] % mod1 + mod1) % mod1;
}
int Get2(int L, int R) {
	return (sum2[R] - sum2[L - 1] * h2[R - L + 1] % mod2 + mod2) % mod2;
} 
int lowbit(int x) {
	return x & (-x);
}
int c[N];
int query(int x) {
	x++;
	int res = 0;
	for(int i = x; i; i -= lowbit(i)) res += c[i];
	return res;
}
void add(int x, int y) {
	x++;
	for(int i = x; i <= 27; i += lowbit(i)) c[i] += y;
}
signed main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0); 
    cin >> T;
    while(T--) {
    	ans = 0;
    	cin >> s;
    	n = s.length();
    	s = " " + s;
    	for(int i = 0; i <= n + 1; i++) suf[i] = pre[i] = sum1[i] = sum2[i] = h1[i] = h2[i] = 0;
    	for(int i = 1; i <= 27; i++) {
    		vis[i] = 0;
    		c[i] = 0;
		} 
    	for(int i = 1; i <= n; i++) {
    		vis[s[i] - 'a' + 1]++;
    		pre[i] = pre[i - 1];
			if(vis[s[i] - 'a' + 1] % 2 == 0)  pre[i]--;
			else pre[i]++;
		}
		for(int i = 1; i <= 27; i++) vis[i] = 0;
		for(int i = n; i >= 1; i--) {
			vis[s[i] - 'a' + 1]++;
    		suf[i] = suf[i + 1];
			if(vis[s[i] - 'a' + 1] % 2 == 0)  suf[i]--;
			else suf[i]++;
		}
		h1[0] = h2[0] = 1;
		for(int i = 1; i <= n; i++) {
			sum1[i] = (sum1[i - 1] * base1 % mod1 + s[i] - 'a' + 1) % mod1;
			h1[i] = h1[i - 1] * base1 % mod1;
			sum2[i] = (sum2[i - 1] * base2 % mod2 + s[i] - 'a' + 1) % mod2;
			h2[i] = h2[i - 1] * base2 % mod2;
		}
		add(pre[1], 1);
		for(int i = 2; i < n; i++) { //AB:[1, i]
			for(int j = i; j < n; j += i) { //ABAB...AB:[1,j]
				if(Get1(j - i + 1, j) != Get1(1, i) || Get2(j - i + 1, j) != Get2(1, i)) break;
				ans += query(suf[j + 1]);
			}
			add(pre[i], 1);
		}
		cout << ans << endl;
	}
	return 0;
}