#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAXN = 3e4 + 5;
const int LB = 14 + 2;
const int inf = 0x3f3f3f3f;

int lb[MAXN];

struct SA {
    int rnk1[MAXN], rnk2[MAXN];
    int sa[MAXN], *rnk, *lst_rnk, st[MAXN][LB], sa_k;
    SA(void): rnk(rnk1), lst_rnk(rnk2) {}
    inline bool sa_same(int x, int y) {
        return lst_rnk[x] == lst_rnk[y] && lst_rnk[x + sa_k] == lst_rnk[y + sa_k];
    }
    inline void build(char s[], int n) {
        static int t[MAXN];
        int m = 3e2;
        memset(t, 0, (m + 1) << 2);

        for (int i = 1; i <= n; ++i)
            ++t[rnk[i] = s[i]];

        for (int i = 1; i <= m; ++i)
            t[i] += t[i - 1];

        for (int i = n; i >= 1; --i)
            sa[t[rnk[i]]--] = i;

        rnk[0] = lst_rnk[0] = rnk[n + 1] = lst_rnk[n + 1] = -1;

        if (n == 1)
            rnk[1] = 1;

        if (m == n)
            ++m;

        for (int &k = sa_k = 1; m != n; k <<= 1) {
            static int id[MAXN];
            int *w = lst_rnk, cur = 0;

            for (int i = n - k + 1; i <= n; ++i)
                id[++cur] = i;

            for (int i = 1; i <= n; ++i)
                if (sa[i] > k)
                    id[++cur] = sa[i] - k;

            memset(t, 0, (m + 1) << 2);

            for (int i = 1; i <= n; ++i)
                ++t[w[i] = rnk[id[i]]];

            for (int i = 1; i <= m; ++i)
                t[i] += t[i - 1];

            for (int i = n; i >= 1; --i)
                sa[t[w[i]]--] = id[i];

            m = 0;
            swap(lst_rnk, rnk);

            for (int i = 1; i <= n; ++i)
                rnk[sa[i]] = sa_same(sa[i], sa[i - 1]) ? m : ++m;
        }

        for (int i = 1, k = 0; i <= n; ++i) {
            if (rnk[i] == n) {
                st[n][0] = k = 0;
                continue;
            }

            if (k)
                --k;

            int j = sa[rnk[i] + 1];

            while (s[i + k] == s[j + k])
                ++k;

            st[rnk[i]][0] = k;
        }

        for (int i = n; i >= 1; --i)
            for (int j = 1; i + (1 << j) - 1 <= n; ++j)
                st[i][j] = min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
    }
    inline int get_min(int l, int r) {
        int k = lb[r - l + 1];
        return min(st[l][k], st[r - (1 << k) + 1][k]);
    }
    inline int lcp(int x, int y) {
        if (x == y)
            return inf;

        x = rnk[x];
        y = rnk[y];
        return x < y ? get_min(x, y - 1) : get_min(y, x - 1);
    }
    inline int operator [](const int x) const {
        return sa[x];
    }
} pre_sa, suf_sa;

int n;
char s[MAXN];
int f[MAXN], g[MAXN];

inline void build(void) {
    suf_sa.build(s, n);
    reverse(s + 1, s + n + 1);
    pre_sa.build(s, n);
    reverse(s + 1, s + n + 1);
}
inline int lcs(int x, int y) {
    return pre_sa.lcp(n - x + 1, n - y + 1);
}
inline int lcp(int x, int y) {
    return suf_sa.lcp(x, y);
}

inline void upd(int a[], int l, int r) {
    if (l <= r)
        ++a[l], --a[r + 1];
}

void solve(void) {
    scanf("%s", s + 1);
    n = strlen(s + 1);

    build();

    for (int i = 1; i <= n + 1; ++i)
        f[i] = g[i] = 0;

    for (int k = 1; k <= n; ++k)
        for (int i = 1; i + k <= n; i += k) {
            int j = i + k;
            int l = i - min(lcs(i, j), k) + 1, r = j + min(lcp(i, j), k) - 1;
            upd(g, l, r - 2 * k + 1);
            upd(f, l + 2 * k - 1, r);
        }

    for (int i = 1; i <= n; ++i)
        f[i] += f[i - 1], g[i] += g[i - 1];

    ll ans = 0;

    for (int i = 1; i < n; ++i)
        ans += (ll)f[i] * g[i + 1];

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

int main(void) {
    lb[0] = -1;

    for (int i = 2; i < MAXN; ++i)
        lb[i] = lb[i >> 1] + 1;

    int T;
    scanf("%d", &T);

    while (T--)
        solve();

    return 0;
}