rt，没用 exkmp 做

把 #define int long long 去掉后就 WA 了，哈希还是负数，感觉还是有细节错误，求调

#include<bits/stdc++.h>
using namespace std;
#define int long long

const int nr = (1 << 20) + 1;
const int P = 31;
const int Mod = 1e9 + 7;
int n, powp[nr], PreHash[nr];
int precnt[nr][27], sufcnt[nr][27];
int preodd[nr], sufodd[nr], lowodd[nr][27];
string s;

int Pow(int a, int b)
{
    int res = 1;
    while (b)
    {
        if (b % 2 == 1) res *= a, res %= Mod;
        a *= a, a %= Mod;
        b /= 2;
    }
    return res;
}

void _clear()
{
    for (int i = 0; i <= n + 1; i++) 
    {
        PreHash[i] = powp[i] = preodd[i] = sufodd[i] = 0;
        for (int c = 1; c <= 26; c++) precnt[i][c] = sufcnt[i][c] = lowodd[i][c] = 0;
    }
}

void Init()
{
    _clear();
    powp[0] = 1;
    for (int i = 1; i <= n; i++) powp[i] = powp[i - 1] * P % Mod;
    for (int i = 1; i <= n; i++)
        PreHash[i] = (PreHash[i - 1] + (s[i] - 'a' + 1) * powp[i] % Mod) % Mod;
    for (int i = 1; i <= n; i++)
        for (int c = 1; c <= 26; c++)
            if (s[i] - 'a' + 1 == c) precnt[i][c] = precnt[i - 1][c] + 1;
            else precnt[i][c] = precnt[i - 1][c];
    for (int i = n; i >= 1; i--)
        for (int c = 1; c <= 26; c++)
            if (s[i] - 'a' + 1 == c) sufcnt[i][c] = sufcnt[i + 1][c] + 1;
            else sufcnt[i][c] = sufcnt[i + 1][c];
    for (int i = 1; i <= n; i++)
        for (int c = 1; c <= 26; c++)
            preodd[i] += (precnt[i][c] % 2 == 1), sufodd[i] += (sufcnt[i][c] % 2 == 1);
    for (int c = 0; c <= 26; c++) 
		for (int i = 1; i <= n; i++)
            lowodd[i][c] = lowodd[i - 1][c] + (preodd[i] <= c);
        
}

bool TheSame(int s1, int e1, int s2, int e2)
{ return (PreHash[e1] - PreHash[s1 - 1] + Mod) * Pow(powp[s1 - 1], Mod - 2) % Mod == (PreHash[e2] - PreHash[s2 - 1] + Mod) * Pow(powp[s2 - 1], Mod - 2) % Mod; }

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int t;
    cin >> t;
    while (t--)
    {
        cin >> s;
        n = s.size(), s = " " + s;
        Init();
        int ans = 0;
        for (int ab = 2; ab < n; ab++)
            for (int i = 1; ab * i < n; i++)
            {
                if (!TheSame(1, ab, ab * (i - 1) + 1, ab * i)) break;
                ans += lowodd[ab - 1][sufodd[ab * i + 1]];
			}
        cout << ans << '\n';
    }
    return 0;
}