#include<bits/stdc++.h>
#include<unordered_map>
#include<unordered_set>
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
#define debug(a) cout<<a<<'\n'
#define Pll pair<ll,ll>
#define PII pair<int,int>
#define ft first
#define sd second
#define vec vector
#define pushk push_back
#define ump unordered_map
#define pl p<<1
#define pr p<<1|1
using namespace std;
const int N = 5e3 + 10, M = 2e6 + 10, mod = 1e9+7;
const ll inf = 1e18;
const ld eps = 1e-13;
int mov[4][2] = { {0,1},{1,0},{-1,0},{0,-1} }, dx, dy, _ = 1, __ = 1;
void bout(bool f) {
    if (f)cout << "YES\n";
    else cout << "NO\n";
}
ll n, m, k;
int lcp[N][N];
ll b[N],sum[N];

void ini(){

}
void solve() {
    string s;
    cin>>s;
    n=s.length();
    s='#'+s;
    ll ans=0;
    memset(lcp,0,sizeof(lcp));
    for(int i=n;i>=1;--i) {
        for(int j=n;j>=1;--j) {
            if(s[i]==s[j])lcp[i][j]=lcp[i+1][j+1]+1;
            else lcp[i][j]=0;
        }
    }
    for(int i=1;i<=n;++i) {
        vec<int> v;
        for(int j=i-1;j>=1;--j) {
            if(lcp[i][j]>=i-j)v.pushk(i-j);
        }
        for(int j=0;j<v.size();++j) {
            sum[j+1]=sum[j]+v[j];
        }
        memset(b,0,8*(n+2));
        for(int j=i+1;j<=n;++j) {
            ++b[min(lcp[i][j],j-i-1)];
        }
        ll p=0;
        for(int j=1;j<=n;++j) {
            if(p<v.size()&&v[p]<j)++p;
            ans+=b[j]*(p*j-sum[p]);
        }
    }
    cout<<ans<<'\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
#ifndef ONLINE_JUDGE
    streambuf *cinbp=cin.rdbuf(),*coutbp=cout.rdbuf();
    ifstream fin("in.txt");
    ofstream fout("out.txt");
    cin.rdbuf(fin.rdbuf());
    cout.rdbuf(fout.rdbuf());
#endif
    cin >> _;
    __ = _;
    ini();
    while (_--) {
        solve();
    }
    return 0;
}