#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define vi vector<int>
#define pb push_back
#define eb emplace_back
#define pii pair<int,int>
#define mp make_pair
#define rep( i , a , b ) for( int i = (a) , i##end = b ; i <= i##end ; ++ i )
#define per( i , a , b ) for( int i = (a) , i##end = b ; i >= i##end ; -- i )
#define mem( a ) memset( a , 0 , sizeof (a) )
#define all( x ) x.begin() , x.end()
//#define int long long
typedef long long ll;
const int MAXN = 5e3 + 10;
const int P = 418254373 , Q = 1e9 + 7;
const int bp = 131 , bq = 137;
int n , m;
char ch[MAXN];

#define qm( a , p ) ( (a) < p ? (a) : (a) - p )

pii operator + ( const pii& a , const pii& b ) {
	return mp( qm( a.fi + b.fi , P ) , qm( a.se + b.se , Q ) );
}
pii operator - ( const pii& a , const pii& b ) {
	return mp( qm( a.fi + P - b.fi , P ) , qm( a.se + Q - b.se , Q ) );
}
pii operator * ( const pii& a , const pii& b ) {
	return mp( a.fi * 1ll * b.fi % P , a.se * 1ll * b.se % Q );
}

int Pow( int x , int a , int p ) {
	int ret = 1;
	while( a ) {
		if( a & 1 ) ret = ret * 1ll * x % p;
		x = x * 1ll * x % p , a >>= 1;
	}
	return ret;
}

pii hsh[MAXN] , iv[MAXN] , bs[MAXN];
pii que( int l , int r ) {
	return ( hsh[r] - hsh[l - 1] ) * iv[l - 1];
}

map<pii,int> M;
int re[MAXN][MAXN];

void solve() {
	M.clear();
	scanf("%s",ch + 1);
	n = strlen( ch + 1 );
	rep( i , 1 , n ) hsh[i] = hsh[i - 1] + bs[i] * mp( ch[i] - '0' + 1 , ch[i] - '0' + 1 );
	
	per( p , n , 1 ) {
		per( i , p - 1 , 1 ) if( M.count( que( i , p - 1 ) ) ) {
			re[i][p - i] = M[que( i , p - 1 )];
		}
		rep( i , p , n ) 
			++ M[que( p , i )];
	}
	rep( i , 1 , n ) per( j , n , 1 ) re[i][j] += re[i][j + 1];
	ll res = 0;
	rep( i , 1 , n ) rep( j , i , n ) if( que( i , j ) == que( j + 1 , j + 1 + ( j - i ) ) ) {
		res += re[j + 1][j - i + 2];
	}
	cout << res << endl;
	rep( i , 1 , n ) rep( j , 1 , n ) re[i][j] = 0;
}

signed main() {
	bs[0] = mp( 1 , 1 ) , bs[1] = mp( bp , bq );
	rep( i , 2 , MAXN - 2 ) bs[i] = bs[i - 1] * bs[1];
	iv[0] = mp( 1 , 1 ) , iv[1] = mp( Pow( bp , P - 2 , P ) , Pow( bq , Q - 2 , Q ) );
	rep( i , 2 , MAXN - 2 ) iv[i] = iv[i - 1] * iv[1];
//	freopen("in","r",stdin);
//	freopen("out","w",stdout);
	int T;cin >> T;while( T-- ) solve();
//	solve();
}