#include <bits/stdc++.h>

using namespace std;

const int N = 5010;
int n, lcp[N][N], siz[N]; string S;

inline void solve() {
    cin >> S; n = S.size(), S = "$" + S;
    for(int i = 0; i <= n + 1; i ++) lcp[n + 1][i] = lcp[i][n + 1] = 0;
    for(int i = n; i >= 1; i --) for(int j = n; j >= 1; j --)
        lcp[i][j] = (S[i] == S[j] ? lcp[i + 1][j + 1] + 1 : 0);
    long long ans = 0;
    for(int i = 2; i <= n; i ++) {
        for(int j = 0; j <= n - i + 2; j ++) siz[j] = 0;
        for(int j = i + 3; j <= n; j ++) 
            if(lcp[i][j] >= 2) siz[min(lcp[i][j] - 1, j - i - 2)] ++;
        long long sum = 0, cnt = 0;
        for(int j = n - i + 1; j >= 1; j --) {
            cnt += siz[j], sum += cnt;
            if(j < i && lcp[i - j][i] >= j) ans += sum;
        }
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);

    int T; cin >> T;
    while(T --) solve();    

    return 0;
}