#include<bits/stdc++.h>
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;
#undef contPrint
};
 
#define dbg(x) "[" << #x << ": " << x << "]  "
#define Wa() cerr << "[LINE: " << __LINE__ << "] -> "; debug() << 
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL);

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


char ch[5005];

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

    vector<int> left[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[j].push_back(j - i);
            }
        }
    }
    for(int i = 0; i < len; i++) {
        sort(left[i].begin(), left[i].end());
    }

    vector<int> bit(len+1);
    int bit_tot = 0;
    auto update = [&] (int pos, int val) {
        if(pos == 0 || pos > len) return;
        bit_tot += val;
        while(pos <= len) {
            bit[pos] += val;
            pos += pos & -pos;
        }
    };

    auto get = [&] (int pos) {
        pos--;
        int ret = 0;
        if(pos <= 0) return 0;
        while(pos) {
            ret += bit[pos];
            pos -= pos & -pos;
        }
        return bit_tot - ret;
    };

    i64 ans = 0;
    for(int l = 0; l < len; l++) {
        auto z = z_function(string(ch + l, ch + len));

        bit.assign(len+1, 0);
        bit_tot = 0;
        for(int i = 3; i < len - l; i++) {
            update(z[i], 1);
        }

        int left_idx = 0;

        for(int r = l + 1; r < len; r++) {
            int cur_len = r - l + 1;

            while(left_idx < left[l].size() && left[l][left_idx] < cur_len) {
                left_idx++;
            }

            int right_cnt = get(cur_len);
            ans += left_idx * right_cnt;

            if(r - l + 2 < (int)z.size()) {
                update(z[r - l + 2], -1);
            }
        }
    }

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


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