//qoj3293
#include <bits/stdc++.h>
using namespace std;

const int N = 240010;
int n;
char s[N];
int cc[N], dd[N];

struct suf{
    int m = 128;
    int sa[N], rk[N], cnt[N], pre[N];
    int he[N], st[20][N];
    inline void build(){
        for(int i = 1; i <= n; ++ i){
            s[n+n+1-i+1] = s[i];
        }
        s[n+1] = '|';
        n = n * 2 + 1;
        for(int i = 1; i <= n; ++ i){
            rk[i] = s[i];
            ++ cnt[rk[i]];
        }
        for(int i = 2; i <= m; ++ i){
            cnt[i] += cnt[i-1];
        }
        for(int i = n; i >= 1; -- i){
            sa[cnt[rk[i]]] = i;
            -- cnt[rk[i]];
        }
        for(int k = 1; k <= n; k <<= 1){
            int tot = 0;
            for(int i = n - k + 1; i <= n; ++ i){
                pre[++tot] = i;
            }
            for(int i = 1; i <= n; ++ i){
                if(sa[i] > k){
                    pre[++tot] = sa[i] - k;
                }
            }
            memset(cnt, 0, sizeof(cnt));
            for(int i = 1; i <= n; ++ i){
                ++ cnt[rk[i]];
            }
            for(int i = 2; i <= m; ++ i){
                cnt[i] += cnt[i-1];
            }
            for(int i = n; i >= 1; -- i){
                sa[cnt[rk[pre[i]]]] = pre[i];
                -- cnt[rk[pre[i]]];
                pre[i] = 0;
            }
            swap(rk, pre);
            tot = 1;
            rk[sa[1]] = 1;
            for(int i = 2; i <= n; ++ i){
                if(pre[sa[i]] == pre[sa[i-1]] &&
                   pre[sa[i]+k] == pre[sa[i-1]+k]){
                       rk[sa[i]] = tot;
                } else {
                    rk[sa[i]] = ++ tot;
                }
            }
            if(tot == n){
                break;
            }
            m = tot;
        }
        for(int i = 1, k = 0; i <= n; ++ i){
            if(rk[i] == 1){
                continue;
            }
            if(k){
                -- k;
            }
            while(s[i+k] == s[sa[rk[i]-1]+k]){
                ++ k;
            }
            he[rk[i]] = k;
        }
        for(int i = 1; i <= n; ++ i){
            st[0][i] = he[i];
        }
        for(int j = 1; j < 20; ++ j){
            for(int i = 1; i + (1<<j) - 1 <= n; ++ i){
                st[j][i] = min(st[j-1][i], st[j-1][i+(1<<j-1)]);
            }
        }
        n /= 2;
    }
    int lcp(int x, int y){
        x = rk[x], y = rk[y];
        if(x > y){
            swap(x, y);
        }
        ++ x;
        int k = 31 ^ __builtin_clz(y-x+1);
        return min(st[k][x], st[k][y-(1<<k)+1]);
    }
    int lcs(int x, int y){
        return lcp(n + n + 2 - x, n + n + 2 - y);
    }
} sa;

int main(){
    int T;
    scanf("%d", &T);
    while(T--){
        memset(cc, 0, sizeof(cc));
        memset(s, 0, sizeof(s));
        memset(dd, 0, sizeof(dd));
        memset(sa.sa, 0, sizeof(sa.sa));
        memset(sa.rk, 0, sizeof(sa.sa));
        memset(sa.he, 0, sizeof(sa.sa));
        memset(sa.pre, 0, sizeof(sa.sa));
        memset(sa.cnt, 0, sizeof(sa.sa));
        memset(sa.st, 0, sizeof(sa.st));
        sa.m = 128;
        scanf("%s", s+1);
        n = strlen(s+1);
        // s[n+1] = '|';
        // ++ n;
        sa.build();
        for(int len = 1; len * 2 <= n; ++ len){
            for(int q = len + 1; q <= n; q += len){
                int p = q - len;
                int le = min(len, sa.lcs(p, q));
                int ri = min(len, sa.lcp(p, q));
                if(q - le + 1 <= p + ri){
                    ++ cc[q-le+1+len-1];
                    -- cc[p+ri+len-1+1];
                    ++ dd[p+ri-len];
                    -- dd[q-le-len];
                }
            }
        }
        for(int i = 1; i <= n; ++ i){
            cc[i] += cc[i-1];
        }
        for(int i = n; i >= 1; -- i){
            dd[i] += dd[i+1];
            // printf("%d %d\n", i, dd[i]);
        }
        long long ans = 0;
        for(int i = 1; i < n; ++ i){
            // printf("%d %d %d\n", i, cc[i], dd[i+1]);
            ans = (ans + 1ll * cc[i] * dd[i+1]);
        }
        printf("%lld\n", ans);
    }
    return 0;
}