#include <bits/stdc++.h>
#define int long long

using namespace std;

constexpr int P = 1145141;
constexpr int mod2 = 1E9 + 33;
constexpr int mod = 998244353;
constexpr int N = 5010;
constexpr int Z = 1E9 + 50;

int p[N];
int p2[N];

void solve () {
    string s;
    cin >> s;

    const int n = s.size ();

    s = " " + s;

    vector <int> Hash (n + 1);
    for (int i = 1; i <= n; i ++) {
        Hash[i] = (Hash[i - 1] * P + s[i]) % mod;
    }
    vector <int> Hash2 (n + 1);
    for (int i = 1; i <= n; i ++) {
        Hash2[i] = (Hash2[i - 1] * P + s[i]) % mod2;
    }

    auto get = [&] (int l, int r) {
        int len = r - l + 1;
        int x = (Hash[r] - Hash[l - 1] * p[len] % mod + mod) % mod;
        int y = (Hash2[r] - Hash2[l - 1] * p2[len] % mod2 + mod2) % mod2;
        return x * Z + y;
    };

    vector <vector <int>> a (n + 1);
    for (int i = 2; i <= n; i ++) {
        for (int j = 1; j < i; j ++) {
            if (i - j > n - i + 1) {
                break;
            }
            int len = i - j;
            if (get (j, i - 1) == get (i, i + len - 1)) {
                a[i].push_back (j);
            }
        }
    }

    map <int, vector <pair <int, int>>> mp;
    for (int l = 1; l <= n; l ++) {
        for (int r = l; r <= n; r ++) {
            mp[get (l, r)].push_back ({l, r});
        }
    }

    vector <vector <vector <pair <int, int>>>> mp2 (n + 1);
    for (auto [_, v] : mp) {
        mp2[v.back ().second - v.back ().first + 1].push_back (v);
    }

    vector <int> d (n + 1);
    for (int i = 1; i <= n; i ++) {
        d[i] = max (0LL, (int)(a[i].size ()) - 1) ;
    }

    int ans = 0;
    for (int t = 2; t <= n; t ++) {
        for (auto &v : mp2[t]) {
            const int m = v.size ();
            for (int i = 0, y = 1; i < m - 1; i ++) {
                auto [l, r] = v[i];
                if (r - l + 1 == 1) {
                    break;
                }
                int len = r - l + 1;
                while (d[l] - 1 >= 0 && a[l][d[l] - 1] >= l - len + 1) {
                    d[l] --;
                }           
                int x = d[l];     
                while (y < m && v[y].first < r + 2) {
                    y ++;
                }
                int sum2 = m - y;
                if (v[i + 1].first == r + 1) {
                    sum2 --;
                }
                ans += sum2 * ((int)(a[l].size ()) - x);
            }
        }
    }

    cout << ans << '\n';
}
 
signed main () {
	ios::sync_with_stdio (false);
    cin.tie (nullptr);

    p[0] = 1;
    for (int i = 1; i < N; i ++) {
        p[i] = p[i - 1] * P % mod;
    }
    p2[0] = 1;
    for (int i = 1; i < N; i ++) {
        p2[i] = p2[i - 1] * P % mod2;
    }
    
    int T = 1;
    cin >> T;

    while (T --) {
        solve ();
    }

 	return 0;
}