#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using ull=unsigned long long;
char s[5005];
int lcp[5005][5005],w[5005],w2[5005];
ull sum[5005],mi[5005];
int main(){
    int t;cin>>t;
    *mi=1;for(int i=1;i<5001;i++) mi[i]=mi[i-1]*11;
    while(t--){
        cin>>s;
        int n=strlen(s);
        for(int i=1;i<=n;i++) sum[i]=sum[i-1]+mi[i-1]*(s[i-1]-47);
        for(int i=0;i<=n;i++) for(int j=0;j<=n;j++) lcp[i][j]=0;
        for(int i=n-1;~i;i--) for(int j=n-1;~j;j--) if(s[i]==s[j]) lcp[i][j]=lcp[i+1][j+1]+1;else lcp[i][j]=0;
        ll ans=0;
        for(int i=0;i<n;i++){
            for(int j=i,l=i-1;j<n&&~l;j++,l--) w[j-i+1]=lcp[l][i]>=j-i+1;
            for(int j=1;j<=n;j++) w2[j]=w[j]*j,w[j]+=w[j-1],w2[j]+=w2[j-1];
            for(int j=i+3;j<n;j++) if(lcp[i][j]){
                int l=min({j-i-2,lcp[i][j]-1,i});
                ans+=(l+1ll)*w[l]-w2[l];
            }
        }
        cout<<ans<<endl;
    }
}