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

typedef long long ll;
const int maxn=5e4+10;

inline int read(){
    int x=0,w=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
    while(c<='9'&&c>='0'){x=(x<<3)+(x<<1)+c-'0';c=getchar();}
    return x*w;
}

int t;
int n;
struct SuffixArray{
    char s[maxn];
    int sa[maxn],rk[maxn<<1],cnt[maxn],oldsa[maxn],oldrk[maxn<<1],tmp[maxn];
    int height[maxn];
    int st[maxn][18];
    inline bool cmp(int x,int y,int l){
        return oldrk[x]==oldrk[y]&&oldrk[x+l]==oldrk[y+l];
    }
    inline void init(){
        memset(s,0,sizeof(s));
        memset(sa,0,sizeof(sa));
        memset(rk,0,sizeof(rk));
        memset(cnt,0,sizeof(cnt));
        memset(oldsa,0,sizeof(oldsa));
        memset(oldrk,0,sizeof(oldrk));
        memset(tmp,0,sizeof(tmp));
        memset(height,0,sizeof(height));
        memset(st,0,sizeof(st));
    }
    inline void build(){
        int siz=max(n,127);
        for(int i=1;i<=n;++i) ++cnt[rk[i]=s[i]];
        for(int i=1;i<=siz;++i) cnt[i]+=cnt[i-1];
        for(int i=n;i>=1;--i) sa[cnt[rk[i]]--]=i;
        for(int l=1,k;;l<<=1){
            k=0;
            for(int i=n;i+l>n;--i) oldsa[++k]=i;
            for(int i=1;i<=n;++i) if(sa[i]>l) oldsa[++k]=sa[i]-l;
            memset(cnt,0,sizeof(cnt));
            for(int i=1;i<=n;++i) ++cnt[tmp[i]=rk[oldsa[i]]];
            for(int i=1;i<=siz;++i) cnt[i]+=cnt[i-1];
            for(int i=n;i>=1;--i) sa[cnt[tmp[i]]--]=oldsa[i];
            for(int i=1;i<=n;++i) oldrk[i]=rk[i];
            k=0;
            for(int i=1;i<=n;++i) rk[sa[i]]=cmp(sa[i],sa[i-1],l)?k:++k;
            if(k==n) break;
            siz=k;
        }   
        for(int i=1,k=0;i<=n;++i){
            if(k) --k;
            while(s[i+k]==s[sa[rk[i]-1]+k]) ++k;
            height[rk[i]]=k;
            st[rk[i]][0]=k;
        }
        for(int k=1;k<=16;++k){
            for(int i=1;i+(1<<k)-1<=n;++i){
                st[i][k]=min(st[i][k-1],st[i+(1<<k-1)][k-1]);
            }
        }
    }
    inline int query(int l,int r){
        int rkl=min(rk[l],rk[r]),rkr=max(rk[l],rk[r]);
        ++rkl;
        int k=log2(rkr-rkl+1);
        return min(st[rkl][k],st[rkr-(1<<k)+1][k]);
    }
}SA1,SA2;

int f[maxn],g[maxn];
ll ans;
int main(){
    t=read();
    while(t--){
        SA1.init();
        SA2.init();
        scanf("%s",SA1.s+1);
        n=strlen(SA1.s+1);
        for(int i=1;i<=n;++i) SA2.s[i]=SA1.s[n-i+1];
        SA1.build();
        SA2.build();
        memset(f,0,sizeof(f));
        memset(g,0,sizeof(g));
        for(int l=1;l*2<=n;++l){
            // printf("***l=%d***\n",l);
            for(int i=0;(i+1)*l+1<=n;++i){
                int x=i*l+1,y=(i+1)*l+1;
                // printf("(%d %d) ",x,y);
                int lcp=SA1.query(x,y),lcs=SA2.query(n-x+1,n-y+1);
                // printf("lcs=%d lcp=%d\n",lcs,lcp);
                if(lcp+lcs-1<l) continue;
                int L=x-lcs+1,R=y+lcp-1-2*l+1;
                if(L<x-l+1) L=x-l+1;
                if(R>x) R=x;
                // printf("[%d %d] ",L,R);
                ++f[L],--f[R+1];
                L=x-lcs+1+2*l-1,R=y+lcp-1;
                if(L<y) L=y;
                if(R>y+l-1) R=y+l-1;
                // printf("[%d %d]\n",L,R);
                ++g[L],--g[R+1];
            }
        }
        for(int i=1;i<=n;++i) f[i]+=f[i-1],g[i]+=g[i-1];
        // for(int i=1;i<=n;++i) printf("%d %d\n",f[i],g[i]);
        ans=0;
        for(int i=1;i<n;++i) ans+=1ll*g[i]*f[i+1];
        printf("%lld\n",ans);
    }
    return 0;
}