#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx,avx2,fma")

#include <bits/stdc++.h>

using namespace std; const int maxn = 1e4 + 5, maxm = 5e3 + 5; typedef long long ll;

int tot = 1, lst = 1, ch[maxn][26], len[maxn], fa[maxn];

inline void insert(char c)
{
    int p = lst, q = ++tot; lst = q, len[q] = len[p] + 1; while (p && !ch[p][c]) ch[p][c] = q, p = fa[p];
    if (!p) { fa[q] = 1; return; }
    int x = ch[p][c]; if (len[x] == len[p] + 1) { fa[q] = x; return; }
    int y = ++tot; len[y] = len[p] + 1, memcpy(ch[y], ch[x], sizeof(int) * 26), fa[y] = fa[x], fa[q] = fa[x] = y;
    while (p && ch[p][c] == x) ch[p][c] = y, p = fa[p];
}

inline void clear()
{
    memset(ch, 0, sizeof(int) * 26 * (tot + 1));
    memset(len, 0, sizeof(int) * (tot + 1));
    memset(fa, 0, sizeof(int) * (tot + 1));
    tot = lst = 1;
}

int n;

char s[maxn];

int hs[maxm][maxm];

int zu[maxm][maxm];

int sm[maxn];

inline void solve()
{
    // scanf("%d", &n);
    scanf("%s", s + 1), n = strlen(s + 1);
    clear();
    for (int i = 1; i <= n; i++) insert(s[i] - '0');
    // for (int i = 1; i <= n; i++)
    // {
    //     int u = 1;
    //     for (int j = i; j <= n; j++)
    //     {
    //         u = ch[u][s[j] - '0'];
    //         // assert(len[u] >= j - i + 1);
    //         while (len[fa[u]] >= j - i + 1) u = fa[u]/*, cerr << i << ' ' << j << ' ' << u << ' ' << fa[u] << ' ' << len[u] << endl*/;
    //         hs[i][j] = u;
    //     }
    // }
    for (int i = 1, u = 1; i <= n; i++)
    {
        u = ch[u][s[i] - '0'];
        for (int j = 1, v = u; j <= i; j++)
        {
            while (len[fa[v]] >= i - j + 1) v = fa[v];
            hs[j][i] = v;
        }
    }
    for (int i = 1; i <= n; i++)
    {
        zu[i][0] = 0;
        for (int j = 1; j < i && j <= n - i + 1; j++)
        {
            if (hs[i - j][i - 1] == hs[i][i + j - 1])
            {
                zu[i][++zu[i][0]] = j;
            }
        }
    }
    ll ans = 0;
    for (int l = n; l; l--)
    {
        for (int i = 1; i + l - 1 <= n; i++)
        {
            // if (sm[hs[i][i + l - 1]])
            // {
            //     cerr << "! " << i << ' ' << i + l - 1 << endl;
            // }
            ans += sm[hs[i][i + l - 1]];
            if (i > l)
            {
                int j = i - l, u = hs[i - l][i - 1];
                while (zu[j][0] && zu[j][zu[j][0]] >= l) zu[j][0]--;
                sm[u] += zu[j][0];
            }
        }
        for (int i = 1; i + l - 1 <= n; i++) sm[hs[i][i + l - 1]] = 0;
    }
    printf("%lld\n", ans);
}

int main()
{
    int Tt; scanf("%d", &Tt); while (Tt--) solve();
    return 0;
}