#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];
ull sum[5005],mi[5005];
inline bool check(int l1,int r1,int l2,int r2){
    return sum[r2+1]-sum[l2]==(sum[r1+1]-sum[l1])*mi[r2-r1];
}
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);
        ull mul=1;
        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]=check(l,i-1,i,j);
            for(int j=1;j<=n;j++) w[j]+=w[j-1];
            for(int j=i+2;j<n;j++){
                int l=min({j-i-2,lcp[i][j]-1,i});
                ans+=w[l];
            }
        }
        cout<<ans<<endl;
    }
}