#include<bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
typedef long long ll;
using namespace std;
typedef pair<int,int> pii;

const int mod=998244353;
inline int add(int x,int y){int ret=x+y;if(ret>=mod)ret-=mod;return ret;}
inline int sub(int x,int y){int ret=x-y;if(ret<0)ret+=mod;return ret;}
inline int mul(int x,int y){return ((ll)x*y)%mod;}
inline int step(int base,int pw){int ret=1;while(pw){if(pw&1)ret=mul(ret,base);base=mul(base,base);pw>>=1;}return ret;}
inline int invv(int x){return step(x,mod-2);}


const int maxn=5010;

string sp;
int n;
int ZR[maxn*2],Z[maxn*2];
void get_z(string &s,int pos){

    int l=0;
    int r=-1;
    for(int i=1;i<s.size();i++){

        if(i>r){
            l=i;
            r=l-1;
            while(r+1<s.size() && s[r+1-l]==s[r+1])r++;
            ZR[i]=r-l+1;
        }
        else{

            if(i+ZR[i-l]-1>=r){
                l=i;
                while(r+1<s.size() && s[r+1-l]==s[r+1])r++;
                ZR[i]=r-l+1;
            }
            else{
                ZR[i]=ZR[i-l];
            }

        }

    }


    for(int i=pos;i<pos+n;i++)Z[i-pos]=ZR[i];
    Z[n]=0;
}

int cnt[maxn*2];
ll solve(int pos){

    string p=sp.substr(pos,sp.size()-pos)+'$'+sp;
    get_z(p,sp.size()-pos+1);

    ll ret=0;
    ll leftcnt=0;
    ll lp=pos;
    ll rightcnt=0;
    ll rp=pos;

    for(int i=0;i<=n;i++)cnt[i]=0;
    for(int i=pos+2;i<n;i++){
        cnt[Z[i]]++;
    }
    cnt[0]=cnt[1]=0;
    for(int i=2;i<=n;i++)rightcnt+=cnt[i];


    for(int i=pos+1;i<n;i++){

        if(lp-1>=0){
            lp--;
            if(lp+Z[lp]>=pos)leftcnt++;
        }

        if(rp+1<n){
            rp++;
            if(Z[rp+1]>=rp-pos && Z[rp+1]>=2){
                //printf("%d %d %d PSKID\n",rp+1,Z[rp+1],rp-pos);
                rightcnt--;
            }
            cnt[Z[rp+1]]--;
            if(rp-pos>=2){
               // printf("%d %lld SKIDAJ\n",rp-pos,cnt[rp-pos]);
                rightcnt-=cnt[rp-pos];
            }
        }

        ///printf("%d | %d | %lld %lld\n",pos,i,leftcnt,rightcnt);

        ret+=leftcnt*rightcnt;

    }

    return ret;
}

int main(){

    ///freopen("test.txt","r",stdin);

    int t;
    scanf("%d",&t);
    while(t--){

        cin>>sp;
        n=sp.size();
        ll rez=0;
        for(int i=0;i<n;i++){
            rez+=solve(i);
        }

        printf("%lld\n",rez);
    }


    return 0;
}