#include<bits/stdc++.h>
#include <cmath>
using namespace std;

using i64 = long long;
using u64 = unsigned long long;

struct debug {
#define contPrint { *this << "["; \
        int f = 0; for(auto it : x) { *this << (f?", ":""); *this << it; f = 1;} \
        *this << "]"; return *this;}
 
    ~debug(){cerr << endl;}
    template<class c> debug& operator<<(c x) {cerr << x; return *this;}
    template<class c, class d>
    debug& operator<<(pair<c, d> x) {*this << "(" << x.first << ", " << x.second << ")"; 
        return *this;}
    template<class c> debug& operator<<(vector<c> x) contPrint;
    template<class c> debug& operator<<(deque<c> x) contPrint;
    template<class c> debug& operator<<(set<c> x) contPrint;
    template<class c> debug& operator<<(multiset<c> x) contPrint;
    template<class c, class d> debug& operator<<(map<c, d> x) contPrint;
    template<class c, class d> debug& operator<<(unordered_map<c, d> x) contPrint;
#undef contPrint
};

#define dbg(x) "[" << #x << ": " << x << "]  "
#define Wa() cerr << "[LINE: " << __LINE__ << "] -> "; debug() << 
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL);

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;

const i64 RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
struct chash {
    i64 operator()(i64 x) const { return x ^ RANDOM; }
};

gp_hash_table<i64, int, chash> cnt;

const int N = 5005;
const int MOD1 = 1e9 + 7;
const int MOD2 = 1e9 + 9;
const int P1 = 31;
const int P2 = 23;

char ch[N];

i64 add(i64 x, i64 y, int mod) {
    return (x + y + mod) % mod;
}

i64 mul(i64 x, i64 y, int mod) {
    return (x * y) % mod;
}

vector<int> z_function(string s) {
    int n = s.size();
    vector<int> z(n);
    int l = 0, r = 0;
    for(int i = 1; i < n; i++) {
        if(i < r) {
            z[i] = min(r - i, z[i - l]);
        }
        while(i + z[i] < n && s[z[i]] == s[i + z[i]]) {
            z[i]++;
        }
        if(i + z[i] > r) {
            l = i;
            r = i + z[i];
        }
    }
    return z;
}

void solve()
{
    scanf("%s", ch);
    int len = strlen(ch);

    vector<int> p_p1(len+1);
    p_p1[0] = 1;
    for(int i = 1; i <= len; i++) p_p1[i] = mul(p_p1[i-1], P1, MOD1);

    vector<int> p_p2(len+1);
    p_p2[0] = 1;
    for(int i = 1; i <= len; i++) p_p2[i] = mul(p_p2[i-1], P2, MOD2);

    vector<int> left_mat[len];
    for(int i = 0; i < len; i++) {
        auto z = z_function(string(ch + i, ch + len));
        for(int j = i + 1; j < len; j++) {
            if(z[j-i] >= j - i) {
                left_mat[j].push_back(j-i);
            }
        }
        // Wa() dbg(i) dbg(z);
    }

    vector<int> qsum[len];
    for(int i = 0; i < len; i++) {
        sort(left_mat[i].begin(), left_mat[i].end());
        // Wa() dbg(i) dbg(left_mat[i]);
        // int s = 0;
        // for(int j : left_mat[i]) {
        //     // s += i - j + 1;
        //     s += 1;
        //     qsum[i].push_back(s);
        // }
    }

    // unordered_map<i64, int> cnt;
    i64 ans = 0;
    for(int r = len-1; r >= 0; r--) {
        i64 h1 = (ch[r] - '0' + 1);
        i64 h2 = (ch[r] - '0' + 1);

        i64 cur_hash = h1 * MOD2 + h2;

        for(int l = r-1; l >= 0; l--) {
            h1 = add(h1, mul(ch[l] - '0' + 1, p_p1[r - l], MOD1), MOD1);
            h2 = add(h2, mul(ch[l] - '0' + 1, p_p2[r - l], MOD2), MOD2);
            cur_hash = h1 * MOD2 + h2;

            int idx = lower_bound(left_mat[l].begin(), left_mat[l].end(), r - l + 1) - left_mat[l].begin();

            auto it = cnt.find(cur_hash);

            // if(idx >= 0) {
                // ans += 1LL * qsum[l][idx] * cnt[cur_hash];
            if(it != cnt.end()) {
                ans += 1LL * idx * cnt[cur_hash];
            }
                // Wa() dbg(idx) dbg(qsum[l][idx]) dbg(cnt[cur_hash]) dbg(r) dbg(l) dbg(cur_hash);
            // }
        }

        h1 = 0;
        h2 = 0;
        for(int rr = r + 1; rr < len; rr++) {
            h1 = mul(h1, P1, MOD1);
            h1 = add(h1, ch[rr] - '0' + 1, MOD1);

            h2 = mul(h2, P2, MOD2);
            h2 = add(h2, ch[rr] - '0' + 1, MOD2);

            // cnt[h1 * MOD2 + h2] += (len - rr);
            cnt[h1 * MOD2 + h2] += 1;
        }

        // Wa() dbg(r) dbg(cnt);
    }

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

int main() 
{
    int T;
    scanf("%d", &T);
    while(T--) {
        solve();
    }
}