#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 3e4;
const int LG = 15;
int T,n;
int lg2[N + 5];
int a[N + 5],b[N + 5];
long long ans;
struct SuffixArray
{
    int n,m;
    char a[N + 5];
    int sa[N + 5],rk[N * 2 + 5],tpr[N * 2 + 5],c[N + 5],height[N + 5];
    int st[N + 5][LG + 5];
    void build()
    {
        memset(sa,0,sizeof sa);
        memset(rk,0,sizeof rk);
        memset(tpr,0,sizeof tpr);
        n = strlen(a + 1),m = 127;
        memset(c,0,sizeof c);
        for(register int i = 1;i <= n;++i)
            ++c[rk[i] = a[i]];
        for(register int i = 1;i <= m;++i)
            c[i] += c[i - 1];
        for(register int i = n;i;--i)
            sa[c[rk[i]]--] = i;
        for(register int w = 1,p = 0;p < n;w <<= 1,m = p)
        {
            p = 0;
            for(register int i = 1;i <= w;++i)
                tpr[++p] = n - w + i;
            for(register int i = 1;i <= n;++i)
                if(sa[i] > w)
                    tpr[++p] = sa[i] - w;
            memset(c,0,sizeof c);
            for(register int i = 1;i <= n;++i)
                ++c[rk[i]];
            for(register int i = 1;i <= m;++i)
                c[i] += c[i - 1];
            for(register int i = n;i;--i)
                sa[c[rk[tpr[i]]]--] = tpr[i];
            swap(rk,tpr),rk[sa[1]] = p = 1;
            for(register int i = 2;i <= n;++i)
                rk[sa[i]] = tpr[sa[i]] == tpr[sa[i - 1]] && tpr[sa[i] + w] == tpr[sa[i - 1] + w] ? p : ++p;
        }
        for(register int i = 1,k = 0;i <= n;++i)
        {
            k -= (bool)k;
            for(;i + k <= n && sa[rk[i] - 1] + k <= n && a[i + k] == a[sa[rk[i] - 1] + k];++k);
            height[rk[i]] = st[rk[i]][0] = k;
        }
        for(register int i = 1;i <= LG;++i)
            for(register int j = 1;j + (1 << i) - 1 <= n;++j)
                st[j][i] = min(st[j][i - 1],st[j + (1 << i - 1)][i - 1]);
    }
    int query(int l,int r)
    {
        l = rk[l],r = rk[r];
        if(l > r)
            swap(l,r);
        ++l;
        int lg = lg2[r - l + 1];
        return min(st[l][lg],st[r - (1 << lg) + 1][lg]);
    }
} s,t;
int main()
{
    for(register int i = 2;i <= N;++i)
        lg2[i] = lg2[i / 2] + 1;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%s",s.a + 1);
        n = strlen(s.a + 1);
        for(register int i = 1;i <= n;++i)
            t.a[i] = s.a[n - i + 1];
        s.build(),t.build();
        memset(a,0,sizeof a),memset(b,0,sizeof b);
        for(register int w = 1;w <= n / 2;++w)
            for(register int i = w;i <= n;i += w)
            {
                int l = i,r = i + w;
                int lcp = s.query(l,r),lcs = t.query(n - r + 2,n - l + 2);
                lcp = min(lcp,w),lcs = min(lcs,w - 1);
                if(lcp + lcs >= w)
                    ++b[l - lcs],--b[l - w + lcp + 1],
                    ++a[r + w - lcs - 1],--a[r + lcp];
            }
        for(register int i = 1;i <= n;++i)
            a[i] += a[i - 1],b[i] += b[i - 1];
        ans = 0;
        for(register int i = 1;i < n;++i)
            ans += a[i] * b[i + 1];
        printf("%lld\n",ans);
    }
}