#include <bits/stdc++.h>
using namespace std;
#define N 300010
inline int read() {
    int x = 0;
    char ch = getchar();

    while (!isdigit(ch))
        ch = getchar();

    while (isdigit(ch))
        x = x * 10 + ch - '0', ch = getchar();

    return x;
}
struct SuffixArray {
    char s[N];
    int a[N], b[N], sa[N], tax[N], hgt[N], Log[N], f[21][N];
    inline void sort(int *a, int *b, int n, int m) {
        for (int i = 1; i <= m; i++)
            tax[i] = 0;

        for (int i = 1; i <= n; i++)
            tax[a[i]]++;

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

        for (int i = n; i >= 1; i--)
            sa[tax[a[b[i]]]--] = b[i];
    }
    inline int cmp(int *f, int x, int y, int k) {
        return f[x] == f[y] && f[x + k] == f[y + k];
    }
    inline void build(char *s, int n) {
        int m = 0;
        memset(sa, 0, sizeof(sa));
        memset(a, 0, sizeof(a));
        memset(b, 0, sizeof(b));
        memset(tax, 0, sizeof(tax));
        memset(hgt, 0, sizeof(hgt));

        for (int i = 1; i <= n; i++)
            m = max(m, a[i] = s[i] - '0'), b[i] = i;

        sort(a, b, n, m);

        for (int p = 0, j = 1; p < n; j <<= 1, m = p) {
            p = 0;

            for (int i = 1; i <= j; i++)
                b[++p] = n - j + i;

            for (int i = 1; i <= n; i++)
                if (sa[i] > j)
                    b[++p] = sa[i] - j;

            sort(a, b, n, m), swap(a, b), a[sa[1]] = p = 1;

            for (int i = 2; i <= n; i++)
                a[sa[i]] = cmp(b, sa[i], sa[i - 1], j) ? p : ++p;

            // printf("%d\n",p);
        }

        // for (int i=1;i<=n;i++) printf("%d ",sa[i]);
        for (int i = 1, j = 0; i <= n; i++) {
            if (j)
                j--;

            while (s[i + j] == s[sa[a[i] - 1] + j])
                j++;

            hgt[a[i]] = j;
        }

        // for (int i=1;i<=n;i++) printf("%d ",a[i]);puts("");
        buildST(n);
    }
    inline void buildST(int n) {
        Log[0] = -1;

        for (int i = 1; i <= n; i++)
            f[0][i] = hgt[i], Log[i] = Log[i >> 1] + 1;

        for (int j = 1; j <= Log[n]; j++)
            for (int i = 1; i + (1 << j) - 1 <= n; i++)
                f[j][i] = min(f[j - 1][i], f[j - 1][i + (1 << j - 1)]);
    }
    inline int ask(int l, int r) {
        int x = min(a[l], a[r]) + 1, y = max(a[l], a[r]), w = Log[y - x + 1];
        return min(f[w][x], f[w][y - (1 << w) + 1]);
    }
} A, B;
char s[N];
int f[N], g[N];
inline void update(int *f, int l, int r) {
    f[l]++, f[r]--;
}
int main() {
    int T = read();

    while (T--) {
        scanf("%s", s + 1);
        int n = strlen(s + 1);
        A.build(s, n), reverse(s + 1, s + n + 1), B.build(s, n);
        memset(f, 0, sizeof(f)), memset(g, 0, sizeof(g));

        for (int len = 1; len <= n / 2; len++) {
            for (int i = len, j = len << 1; j <= n; i += len, j += len) {
                int lcp = min(A.ask(i, j), len), lcs = min(B.ask(n - i + 2, n - j + 2), len - 1);
                int t = lcp + lcs - len + 1;

                if (t > 0)
                    update(g, i - lcs, i - lcs + t), update(f, j + lcp - t, j + lcp);
            }
        }

        long long ans = 0;

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

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

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

    return 0;
}