#include <bits/stdc++.h>
using namespace std;
const int MAXN = (1 << 20);
int n;
string s;
int z[MAXN + 5];
void exKMP(const string &s)
{
    z[0] = 0;
    for (int l = 0, r = 0, i = 1; i < s.length(); i++)
    {

        // s[i...r] == s[i-l...r-l]
        if (i <= r && z[i - l] < r - i + 1)
            z[i] = z[i - l];
        else
        {
            z[i] = max(0, r - i + 1);
            while (i + z[i] < s.length() && s[z[i]] == s[i + z[i]])
                z[i]++;
        }
        if (i + z[i] - 1 > r)
            l = i, r = i + z[i] - 1;
    }
}
// s[0..i] 出现了奇数次的字符的个数
int cnt[MAXN + 5];
// s[i..n-1] 出现了奇数次的字符的个数
int tnc[MAXN + 5];
int temp[30];
void getCntTnc(const string &s)
{
    int len = s.length();
    memset(temp, 0, sizeof(temp));
    cnt[0] = 1;
    temp[s[0] - 'a']++;
    for (int i = 1; i < len; i++)
    {
        cnt[i] = cnt[i - 1];
        int now = s[i] - 'a';
        temp[now]++;
        if (temp[now] % 2 == 0)
            cnt[i]--;
        else
            cnt[i]++;
    }
    memset(temp, 0, sizeof(temp));
    tnc[len - 1] = 1;
    temp[s[len - 1] - 'a']++;
    for (int i = len - 2; i >= 0; i--)
    {
        tnc[i] = tnc[i + 1];
        int now = s[i] - 'a';
        temp[now]++;
        if (temp[now] % 2 == 0)
            tnc[i]--;
        else
            tnc[i]++;
    }
}
//树状数组
long long tr[30];
int lowbit(int x)
{
    return x & (-x);
}
void add(int x)
{
    for (int i = x; i <= 27; i += lowbit(i))
        tr[i]++;
}
long long query(int x)
{
    long long res = 0;
    for (int i = x; i >= 1; i -= lowbit(i))
        res += tr[i];
    return res;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    while (n--)
    {
        cin >> s;
        int len = s.length();
        exKMP(s);
        getCntTnc(s);
        /*
        cout << "--------------\n";
        for (int i = 0; i < s.length(); i++)
            cout << z[i] << " ";
        cout << "\n";
        for (int i = 0; i < s.length(); i++)
            cout << cnt[i] << " ";
        cout << "\n";
        for (int i = 0; i < s.length(); i++)
            cout << tnc[i] << " ";
        cout << "\n";
        */
        memset(tr, 0, sizeof(tr));
        long long ans = 0;
        //枚举循环节长度 cLen
        for (int cLen = 2; cLen <= len - 1; cLen++)
        {
            add(cnt[cLen - 2] + 1);
            //循环节的最多循环次数 cK
            int cK = z[cLen] / cLen + 1;
            if (cLen * cK == len)
                cK--;
            int cKE = cK / 2;   //偶数的循环次数情况数
            int cKO = cK - cKE; //奇数的循环次数情况数

            //(AB)^{cKE}C
            // cnt[i] <= tnc[0] : for i in range(cLen)
            ans += query(tnc[0] + 1) * cKE;
            //(AB)^{cKO}C
            // cnt[i] <= tnc[cLen]
            ans += query(tnc[cLen] + 1) * cKO;
            // cout << cLen << ":" << query(tnc[0]) << "," << cKE << " " << query(tnc[cLen]) << " " << cKO << endl;
        }
        cout << ans << "\n";
    }
    return 0;
}