#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
const int LEN=6e4;
int rk[LEN],rk2[LEN],sa[LEN],cnt[LEN];
int h[LEN];
int nw[LEN];
int loc[LEN];
int st[LEN][16];
const int LG=16;
int lg[LEN];
inline void clr(){memset(cnt,0,sizeof(cnt));}
inline void sct(){
    for(int i=1;i<LEN;i++)
        cnt[i]+=cnt[i-1];
}
inline void SA(string P){
    int m=P.size();
    P=" "+P;
    P=P+(char)(0);
    clr();
    for(int i=1;i<=m;i++)
        rk[i]=P[i],cnt[rk[i]]++,h[i]=0;
    sct();
    for(int i=1;i<=m;i++)
        sa[++cnt[rk[i]-1]]=i;
    for(int p=1;p<m;p<<=1){
        for(int i=1;i<=m;i++)
            rk2[i]=i+p<=m?rk[i+p]:0;
        clr();
        for(int i=1;i<=m;i++)cnt[rk[i]]++;
        sct();
        vector<int>T;
        for(int i=1;i<=m;i++)if(sa[i]+p>m)T.push_back(sa[i]);
        for(int i=1;i<=m;i++)if(sa[i]>p)T.push_back(sa[i]-p);
        for(int x:T)sa[++cnt[rk[x]-1]]=x;
        int cnt=0;
        for(int i=1;i<=m;i++){
            if(i==1||rk[sa[i]]!=rk[sa[i-1]]||rk2[sa[i]]!=rk2[sa[i-1]])
                cnt++;
            nw[sa[i]]=cnt;
        }
        for(int i=1;i<=m;i++)
            rk[i]=nw[i];
    }
    int t=0;
    for(int i=1;i<=m;i++){
        t=max(0ll,h[rk[i-1]]-1);
        if(rk[i]==1){t=0;h[rk[i]]=0;continue;}
        int l=sa[rk[i]-1];
        while(l+t<=m&&i+t<=m&&P[l+t]==P[i+t])t++;
        h[rk[i]]=t;
    }
    for(int i=1;i<=m;i++)st[i][0]=h[i];
    for(int j=1;j<LG;j++)
        for(int i=1;i+(1<<j)-1<=m;i++)
            st[i][j]=min(st[i][j-1],st[i+(1<<j-1)][j-1]);
}
inline int g(int l,int r){
    if(l>r)return 0;
    int p=lg[r-l+1];
    return min(st[l][p],st[r-(1<<p)+1][p]);
}
int n;
inline int lcp(int x,int y){
    if(x<=0||y<=0)return 0;
    
    x=rk[x],y=rk[y];
    if(x>y)swap(x,y);
    return g(x+1,y);
}
inline int lcp_rev(int x,int y){
    if(x<=0||y<=0||x>n||y>n)return 0;
    x=n-x+1,y=n-y+1;
    return lcp(x+n,y+n);
}
inline int lcp_ver(int x,int y){
    if(x<=0||y<=0||x>n||y>n)return 0;
    return lcp(x,y);
    
}
string s;
int bel[LEN];
int A[LEN],B[LEN];
int L[LEN],R[LEN];
signed main(){
    // freopen("uke.in","r",stdin);
    // freopen(".out","w",stdout);
    ios::sync_with_stdio(0);
    int t;
    cin>>t;
    for(int i=2;i<LEN;i++)
    lg[i]=lg[i>>1]+1;
    while(t--){
        string t;
        cin>>t;
        s=t;
        n=s.size();
        reverse(t.begin(),t.end());
        s=s+t;
        SA(s);
        for(int i=1;i<=n;i++)A[i]=B[i]=0;
            // cout<<lcp_ver(5,7)<<" "<<lcp_rev(4,6)<<endl;
        for(int s=1;s<=n;s++){
            int m=0;
            while(++m){
                L[m]=R[m-1]+1;
                R[m]=min(L[m]+s-1,n);
                if(R[m]==n)break;
            }
            L[m+1]=n+1;
            for(int i=2;i<=m;i++){
                int l=min(s,lcp_rev(R[i-1],R[i]));
                int r=min(s-1,lcp_ver(L[i],L[i+1]));
                if(l+r<s)continue;
                int pl=s-r,pr=l;
                
                // cout<<l<<" "<<r<<" "<<L[i]<<" "<<R[i]<<" "<<s<<endl;
                // cout<<pl<<" "<<pr<<" "<<L[i]-pr<<" "<<L[i]-pl<<endl;
                A[L[i]-pr]++;
                A[L[i]-pl+1]--;

                pl=s-pl,pr=s-pr;
                // cout<<pl<<" "<<pr<<" "<<R[i]+pr<<" "<<R[i]+pl<<endl;
                
                B[R[i]+pr]++;
                B[R[i]+pl+1]--;

            }
        }
        for(int i=1;i<=n;i++)A[i]+=A[i-1],B[i]+=B[i-1];
        // for(int i=1;i<=n;i++)
        // cout<<A[i]<<" ";
        // cout<<endl;
        // for(int i=1;i<=n;i++)
        // cout<<B[i]<<" ";
        // cout<<endl;
        int res=0;
        for(int i=2;i<=n-2;i++)
            res+=B[i]*A[i+1];
        cout<<res<<endl;
    }


    cout.flush();
    return 0;
}
/*

*/