#pragma GCC optimize("O3")
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define ull unsigned long long

const int N = 5e3;
const int B = 131;
const int mod=1e9+9;

int n;
char s[N + 5];
int pw[N + 5], h[N + 5];
int f[N + 5][N + 5],I;
//ull query(int l, int r) { 
////	if(l==4854)cout<<"query ["<<l<<","<<r<<"]\n";
//	return (h[r] - pw[r - l + 1] * h[l - 1]); 
//}
int query(int l, int r) { return (h[r] + (ll)(mod - pw[r - l + 1]) * h[l - 1]) % mod; }
ll ans;

const int M=2.5e7+5;
struct HashTable{
	int nxt[M],cnt[M],tot,head[M];
	int stk[M],top;int key[M];
	void clear(){
//		cout<<"tot = "<<tot<<endl;
		for(int i=1;i<=tot;i++)nxt[i]=key[i]=cnt[i]=0;tot=0;
		for(int i=1;i<=top;i++)head[stk[i]]=0;top=0;
	}
	void ins(int x){
		int v=x%M;
//		if(I==4854)cout<<"x = "<<x<<" v = "<<v<<'\n';
		if(head[v]==0)stk[++top]=v,head[v]=++tot,key[tot]=x,cnt[tot]=1;
		else{
			int p=head[v],pre=0;
			while(key[p]!=x&&p){
//				cout<<"p = "<<p<<" pre = "<<pre<<endl;
				pre=p,p=nxt[p];
			}
			if(!p){
				p=++tot;
				if(pre)nxt[pre]=p;
				key[p]=x,cnt[p]=1;
			}
			else cnt[p]++;
		}
	}
	int getcount(int x){
//		cout<<"x = "<<x<<endl;
		int v=x%M;int p=head[v];
		while(p){
			if(key[p]==x)return cnt[p];
			p=nxt[p];
		}
		return 0;
	}
}Map;
//map<int,int>cnt;

void solve() {
//	double W=-clock();
  scanf("%s", s + 1), n = strlen(s + 1);
//  cout<<"n = "<<n<<endl;
  pw[0] = 1;
//  for (int i = 1; i <= n; ++i) pw[i] = pw[i - 1] * B;
//  for (int i = 1; i <= n; ++i) h[i] = h[i - 1] * B + s[i] - '0' + 1;
  for (int i = 1; i <= n; ++i) pw[i] = (ll)pw[i - 1] * B % mod;
  for (int i = 1; i <= n; ++i) h[i] = ((ll)h[i - 1] * B + s[i] - '0' + 1) % mod;
//  puts("input ok");
  Map.clear();
  for (int i = n; i; --i) {
//  	cout<<"i = "<<i<<endl;I=i;
    for (int j = i - 1; j; --j) f[j][i - 1] = Map.getcount(query(j, i - 1));
//    for (int j = i - 1; j; --j) f[j][i - 1] =cnt[query(j, i - 1)];
//    puts("ok");
    for (int j = i; j <= n; ++j) Map.ins(query(i, j));
//    for (int j = i; j <= n; ++j) cnt[query(i, j)]++ ;
  }
  
//  for(int i=1;i<=n;i++)for(int j=i;j<=n;j++)cout<<f[i][j]<<" \n"[j==n];
//  W+=clock();cout<<"hashtable ok time = "<<W<<endl;
  ans = 0;
  for (int i = 1; i <= n; ++i) {
    int cur = 0;
    for (int len = 1; i + len - 1 <= n; ++len) {
      ans += (ll)cur * f[i][i + len - 1];
      if (len <= i - 1 && query(i - len, i - 1) == query(i, i + len - 1)) ++cur;
    }
  }
  printf("%lld\n", ans);
//	cout<<"tot = "<<Map.tot<<endl;
}

int T;

int main() {
#ifdef YUNQIAN
	freopen("B.in","r",stdin);
//	freopen("B1.out","w",stdout);
#endif		
  for (scanf("%d", &T); T; --T) solve();
}