#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <stack>
#include <vector>
#include <queue>
#define ll long long
//#define int ll
using namespace std;
inline int read() {
    int d = 0, f = 1;
    char x = getchar();

    while (x < '0' || x > '9') {
        if (x == '-') {
            f = -1;
        }

        x = getchar();
    }

    while (x >= '0' && x <= '9') {
        d = (d << 1) + (d << 3) + (x - 48);
        x = getchar();
    }

    return d * f;
}
int z[3000010], cnt1[50], cnt2[50], sum[50], n, cnt, now, res, tot, ret;
ll ans;
char s[3000010];
void Z_function(char *s, int len) {
    z[0] = len - 1;

    for (int i = 1, l = -1, r = -1; i < len; i++) {
        if (i <= r)
            z[i] = min(z[i - l], r - i + 1);
        else
            z[i] = 0;

        while (i + z[i] < len && s[z[i]] == s[i + z[i]])
            z[i]++;

        if (i + z[i] > r)
            l = i, r = i + z[i] - 1;
    }
}
int T;
signed main() {
    freopen("string.in", "r", stdin);
    freopen("string.out", "w", stdout);
    T = read();

    while (T--) {
        scanf("%s", s);
        n = strlen(s);
        memset(sum, 0, sizeof(sum));
        memset(cnt1, 0, sizeof(cnt1));
        memset(cnt2, 0, sizeof(cnt2));
        ans = ret = cnt = 0;

        for (int i = 0; i < n; i++)
            cnt1[s[i] - 'a'] ^= 1;

        for (int i = 0; i < 26; i++)
            cnt += cnt1[i];

        Z_function(s, n);
        now = cnt, res = tot = 0;

        for (int i = 1; i < n; i++) {
            if (cnt1[s[i - 1] - 'a'])
                tot -= sum[now--];
            else
                tot += sum[++now];

            cnt1[s[i - 1] - 'a'] ^= 1;
            int k = min(z[i], n - i - 1) / i + 1;
            int c1 = k - (k >> 1), c2 = k >> 1;
            ans += 1ll * tot * c1;

            if (cnt2[s[i - 1] - 'a'])
                res--;
            else
                res++;

            cnt2[s[i - 1] - 'a'] ^= 1;
            sum[res]++;
            ans += 1ll * ret * c2;

            if (res <= now)
                tot++;

            if (res <= cnt)
                ret++;
        }

        printf("%lld\n", ans);
    }

    return 0;
}