求调WA*2

#include<bits/stdc++.h>

using namespace std;
#define int long long
const int maxSize = (1 << 20) + 10;

template<typename T>
void read(T &a) {
    a = 0;
    bool f = false;
    char ch;
    do {
        ch = (char) getchar();
        if (ch == '-')
            f = true;
    } while (ch < '0' || ch > '9');
    do {
        a = (a << 3) + (a << 1) + ch - '0';
        ch = (char) getchar();
    } while (ch >= '0' && ch <= '9');
    if (f) a *= -1;
}

void scan(string &s) {
    s.clear();
    char ch;
    do {
        ch = getchar();
    } while (ch == ' ' || ch == '\n');
    do {
        s += ch;
        ch = getchar();
    } while (ch != ' ' && ch != '\n');
}

int lcp[maxSize];
string s;

void Init() {
    int l = 0, r = 0;
    for (int i = 1; i <= s.size(); i++) {
        if (i <= r && lcp[i - l] <= r - i + 1) {
            lcp[i] = lcp[i - l];
        } else {
            lcp[i] = max(0ll, r - i + 1);
            while (s[lcp[i]] == s[i + lcp[i]] && lcp[i] + i < s.size())lcp[i]++;
        }
        if (i + lcp[i] - 1 > r)l = i, r = i + lcp[i] - 1;
    }
}

bitset<30> odd[maxSize];
int lw[maxSize][30];
int T;
int ans;

signed main() {
    read(T);
    while (T--) {
        ans = 0;
        scan(s);
        for (int i = 0; i < s.size(); i++) {//预处理前缀奇数字符、<= num
            if (i) {
                odd[i] = odd[i - 1];
                for (int j = 0; j < 26; j++)
                    lw[i][j] = lw[i - 1][j];
            }
            odd[i][s[i] - 'a'] = !odd[i][s[i] - 'a'];
            int num = (int) odd[i].count();
            for (int j = num; j < 26; j++)
                lw[i][j]++;
        }
        Init();
        for (int i = 2; i < s.size(); i++) {//截取[0,i)作为AB
            int tms = (lcp[i] / i) + 1;
            if (tms * i == s.size())
                tms--;
            if (tms > 1) {
                int fab = (int) (odd[i - 1]).count();
                int lc = tms * i;
                int fc1 = (int) (odd[s.size() - 1] ^ odd[lc - 1]).count(), num1 = (int) ceil(1.0 * tms / 2);
                int fc2 = (int) (odd[s.size() - 1] ^ odd[lc - 1] ^ odd[i - 1]).count(), num2 = tms / 2;
                ans += lw[i - 2][fc1] * num1 + lw[i - 2][fc2] * num2;
            } else {
                int fc = (int) (odd[s.size() - 1] ^ odd[i - 1]).count();
                ans += lw[i - 2][fc];
            }
        }
        printf("%lld\n", ans);
        for (int i = 0; i < s.size(); i++)odd[i].reset();
        memset(lw, 0, sizeof(lw));
    }
}