// Skyqwq
#include <bits/stdc++.h>

using namespace std;

const int N = 5005;

typedef long long LL;

int n, f[N][N], g[N][N];
LL h[N][N];

char s[N];

void clr() {
	for (int i = 0; i <= n + 1; i++)
		for (int j = 0; j <= n + 1; j++)
			f[i][j] = g[i][j] = h[i][j] = 0;
}

int main() {
    int T; scanf("%d", &T);
    while (T--) {
    	scanf("%s", s + 1);
    	n = strlen(s + 1);
    	for (int i = n; i; i--) {
    		for (int j = n; j; j--) {
    			if (s[i] == s[j])
    				f[i][j] = f[i + 1][j + 1] + 1;
    		}
    	}
    	for (int i = 1; i <= n; i++) {
    		for (int j = 1; j <= n; j++) {
    			if (i - j >= 1 && f[i - j][i] >= j)
    				g[i][j] = 1;
    			g[i][j] += g[i][j - 1];
    			h[i][j] = g[i][j - 1];
    			h[i][j] += h[i][j - 1];
    		}
    	}
    	LL ans = 0;
    	for (int i = 1; i <= n; i++) {
    		for (int j = i + 1; j <= n; j++) {
    			int u = min(f[i][j], j - i - 1);
    			ans += h[i][u];
    		}
    	}
    	printf("%lld\n", ans);
    	clr();
    }
    return 0;
}