#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
template <typename T> inline void read(T &F) {
    int R = 1; F = 0; char CH = getchar();
    for(; !isdigit(CH); CH = getchar()) if(CH == '-') R = -1;
    for(; isdigit(CH); CH = getchar()) F = F * 10 + CH - 48;
    F *= R;
}
inline void file(string str) {
    freopen((str + ".in").c_str(), "r", stdin);
    freopen((str + ".out").c_str(), "w", stdout);
}
const int N = 5e3 + 10;
int f[N][N], pre[N][N], succ[N][N]; LL g[N][N]; char s[N]; int n;
bool check(int l, int r) {
    if(l - (r - l + 1) < 1) return false;
    return succ[l - (r - l + 1)][l] >= r - l + 1;
}
int main() {
    //file("");
    int T; read(T);
    while(T--) {
        scanf("%s", s + 1); n = strlen(s + 1);
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++) {
                if(s[i] == s[j]) pre[i][j] = pre[i - 1][j - 1] + 1;
                else pre[i][j] = 0;
            }
        for(int i = 1; i <= n + 1; i++)
            succ[i][n + 1] = succ[n + 1][i] = 0;
        for(int i = n; i >= 1; i--)
            for(int j = n; j >= 1; j--) {
                if(s[i] == s[j]) succ[i][j] = succ[i + 1][j + 1] + 1;
                else succ[i][j] = 0;
            }
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= i; j++) {
                f[i][j] = f[i][j - 1], g[i][j] = g[i][j - 1];
                if(check(i - j + 1, i)) f[i][j]++, g[i][j] += j;
            }
        }
        LL ans = 0;
        for(int i = 3; i <= n; i++) {
            for(int j = i + 2; j <= n; j++) {
                if(!succ[i][j]) continue;
                //cout << i << ' ' << j << endl;
                int l = min(j - i - succ[i][j] - 1, pre[i - 1][j - 1]); l = max(l, 0);
                //cout << i << ' ' << j << ' ' << l << ' ' << succ[i][j] << ' ' << f[i - 1][l] << endl;
                ans += 1LL * succ[i][j] * f[i - 1][l];
                int r = min(j - i - 2, pre[i - 1][j - 1]);
                if(r > l) ans += 1LL * (j - i - 1) * (f[i - 1][r] - f[i - 1][l]) - 1LL * (g[i - 1][r] - g[i - 1][l]);
            }
        }
        cout << ans << '\n';
    }
    
    #ifdef _MagicDuck
        fprintf(stderr, "# Time: %.3lf s", (double)clock() / CLOCKS_PER_SEC);
    #endif
    return 0;
}