#include <bits/stdc++.h>
#define int long long
using namespace std;
int T;
string s;
int n; // s.length()
// Hash
const int MOD1 = 1000000007, MOD2 = 998244353;
const int P1 = 29, P2 = 31;
int hash1[30005], hash2[30005];
int powP1[30005], powP2[30005];
void initHash(int n)
{
    powP1[0] = powP2[0] = 1;
    for (int i = 1; i <= n; i++)
    {
        hash1[i] = (hash1[i - 1] * P1 + s[i] - 'a' + 1) % MOD1;
        hash2[i] = (hash2[i - 1] * P2 + s[i] - 'a' + 1) % MOD2;
        powP1[i] = powP1[i - 1] * P1 % MOD1;
        powP2[i] = powP2[i - 1] * P2 % MOD2;
    }
    powP1[n + 1] = powP1[n] * P1 % MOD1;
    powP2[n + 1] = powP2[n] * P2 % MOD2;
}
bool hashCmp(int l, int r, int x, int y)
{
    // return [l,r] == [x,y]
    int hash1LR = (hash1[r] - hash1[l - 1] * powP1[r - l + 1] % MOD1 + MOD1) % MOD1;
    int hash2LR = (hash2[r] - hash2[l - 1] * powP2[r - l + 1] % MOD2 + MOD2) % MOD2;
    int hash1XY = (hash1[y] - hash1[x - 1] * powP1[y - x + 1] % MOD1 + MOD1) % MOD1;
    int hash2XY = (hash2[y] - hash2[x - 1] * powP2[y - x + 1] % MOD2 + MOD2) % MOD2;
    return hash1LR == hash1XY && hash2LR == hash2XY;
}
//以 i 结尾有多少个 AA
int f[30005];
//以 i 开头有多少个 AA
int g[30005];
signed main()
{
    // ios::sync_with_stdio(false);
    // cin.tie(0);
    cin >> T;
    while (T--)
    {
        cin >> s;
        n = s.length();
        s = "^" + s + "$";
        initHash(n);
        for (int i = 0; i <= n; i++)
            f[i] = g[i] = 0;
        // 处理 f
        // 枚举参考点间隙长度 L
        for (int L = 1; L < n; L++)
        {
            //枚举相邻参考点
            for (int i = 1, j = i + L; j <= n; i += L, j += L)
            {
                int p, q; // i、j 前/后 最长公共长度
                //二分计算 i,j 前面最长的公共
                int l = 0;
                int r = i;
                p = 0;
                while (l <= r)
                {
                    int mid = (l + r) / 2;
                    // [i - mid + 1, i] == [j - mid + 1, j]
                    if (hashCmp(i - mid + 1, i, j - mid + 1, j))
                    {
                        p = mid;
                        l = mid + 1;
                    }
                    else
                    {
                        r = mid - 1;
                    }
                }
                l = 0;
                r = n - j;
                q = 0;
                while (l <= r)
                {
                    int mid = (l + r) / 2;
                    //[i + 1, i + mid] == [j + 1, j + mid]
                    if (hashCmp(i + 1, i + mid, j + 1, j + mid))
                    {
                        q = mid;
                        l = mid + 1;
                    }
                    else
                    {
                        r = mid - 1;
                    }
                }
                //长度为 L 的可行区间：[j+L-p,j+q] && [j,j+L-1] && [j,n]
                l = max(j + L - p, min(j, n));
                r = min(j + q, min(j + L - 1, n));
                // cout << L << ":" << i << "," << j << "  " << p << "," << q << "\n";
                if (l <= r)
                {
                    // cout << l << "~" << r << endl;
                    f[l]++, f[r + 1]--;
                }
            }
        }
        for (int i = 1; i <= n; i++)
            f[i] += f[i - 1];
        // 处理 g
        // 枚举参考点间隙长度 L
        for (int L = 1; L < n; L++)
        {
            //枚举相邻参考点
            for (int j = n, i = j - L; i >= 1; j -= L, i -= L)
            {
                int p, q; // i、j 前/后 最长公共长度
                //二分计算 i,j 前面最长的公共
                int l = 0;
                int r = i;
                p = 0;
                while (l <= r)
                {
                    int mid = (l + r) / 2;
                    // [i - mid + 1, i] == [j - mid + 1, j]
                    if (hashCmp(i - mid + 1, i, j - mid + 1, j))
                    {
                        p = mid;
                        l = mid + 1;
                    }
                    else
                    {
                        r = mid - 1;
                    }
                }
                l = 0;
                r = n - j;
                q = 0;
                while (l <= r)
                {
                    int mid = (l + r) / 2;
                    //[i + 1, i + mid] == [j + 1, j + mid]
                    if (hashCmp(i + 1, i + mid, j + 1, j + mid))
                    {
                        q = mid;
                        l = mid + 1;
                    }
                    else
                    {
                        r = mid - 1;
                    }
                }
                //长度为 L 的可行区间：[i-p+1,i-L+1+q] && [i-L+1,i] && [1,i-1]
                l = max(i - p + 1, max(i - L + 1, 1LL));
                r = min(i - L + 1 + q, max(i, 1LL));
                // cout << L << ":" << i << "," << j << "  " << p << "," << q << "\n";
                if (l <= r)
                {
                    // cout << l << "~" << r << endl;
                    g[l]++, g[r + 1]--;
                }
            }
        }
        for (int i = 1; i <= n; i++)
            g[i] += g[i - 1];
        /*
        for (int i = 1; i <= n; i++)
            cout << f[i] << " ";
        cout << "\n";
        for (int i = 1; i <= n; i++)
            cout << g[i] << " ";
        cout << "\n";
        */
        int ans = 0;
        // f[i],g[i+1]
        for (int i = 2; i <= n - 2; i++)
            ans += f[i] * g[i + 1];
        cout << ans << "\n";
    }
    return 0;
}