z函数 48pts tle

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int maxn = 1e6 + 500;
int z[maxn], n; string s;
void exkmp() {
	int l = 0, r = 0;
	for (int i = 1; i <= n; ++i) {
		z[i] = 0;
		if (i <= r) z[i] = min(r - i + 1, z[i - l + 1]);
		for (; i + z[i] <= n && s[i + z[i]] == s[1 + z[i]]; ++z[i]);
		if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1;
	}
	for (int i = 1; i <= n; ++i) {
		z[i] = min(z[i], n - i);
	}
}
int cp[26], cs[26];
struct BIT {
	int c[30], lim = 26;
	int lowbit(int x) {return x & (-x);}
	void add(int pos, int delta) {
		for (; pos <= lim; pos += lowbit(pos)) c[pos] += delta;
	}
	int query(int pos) {
		int res = 0;
		for (; pos; pos -= lowbit(pos)) res += c[pos];
		return res;
	}
} bit;
void clear() {
	memset(cp, 0, sizeof cp);
	memset(cs, 0, sizeof cs);
	memset(bit.c, 0, sizeof bit.c);
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
	int T; cin >> T;
	while (T--) {
		cin >> s;
		n = s.size();
		s = " " + s;
		exkmp();
		int tot = 0, fp = 0, fs = 0;
		clear();
		for (int i = 1; i <= n; ++i) ++cs[s[i] - 'a'];
		for (int i = 0; i < 26; ++i) tot += (cs[i] & 1);
		fs = tot;
		int ans = 0;
		for (int i = 1; i < n; ++i) {
			if (++cp[s[i] - 'a'] & 1) ++fp;
			else --fp;
			if (--cs[s[i] - 'a'] & 1) ++fs;
			else --fs;
			if (i > 1) {
				int x = 1 + z[i + 1] / i;
				ans += (x / 2 + (x & 1)) * bit.query(fs + 1) + (x / 2) * bit.query(tot + 1);
			}
			bit.add(fp + 1, 1);
		}
		cout << ans << endl;
	}
	return 0;
}