#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);
            }
        }
    }

    unordered_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});
        }
    }

    int ans = 0;
    for (auto &[_, v] : mp) {
        const int m = v.size ();
        for (int i = 0; i < m - 1; i ++) {
            auto [l, r] = v[i];
            if (r - l + 1 == 1) {
                break;
            }
            int len = r - l + 1;
            int x = lower_bound (a[l].begin (), a[l].end (), l - len + 1) - a[l].begin ();
            int y = lower_bound (v.begin () + i, v.end (), pair <int, int> {r + 2, 0}) - v.begin ();
            int sum2 = m - y;
            // if (l == 2 && r == 3) {
            //     cerr << x << " " << sum2 << " " << m << '\n';
            // }
            if (v[i + 1].first == r + 1) {
                sum2 --;
            }
            // if (l == 2 && r == 3) {
            //     cerr << sum2 << " " << a[l].size () - x << '\n';
            // }
            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;
}