#include <bits/stdc++.h>

using namespace std;

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

const int N = 5e3;
const int B = 131;

int n;
char s[N + 5];
ull pw[N + 5], h[N + 5];
int f[N + 5][N + 5];
ull query(int l, int r) { return (h[r] - pw[r - l + 1] * h[l - 1]); }
ll ans;

const int M=2.5e7+5;
struct HashTable{
	int nxt[M],cnt[M],tot,head[M];
	int stk[M],top;ull key[M];
	void clear(){
		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(ull x){
		int v=x%M;
		if(head[v]==0)stk[++top]=v,head[v]=++tot,key[tot]=x,cnt[tot]=1;
		else{
			int p=head[v];
			while(key[p]!=x)p=nxt[p];
			if(!p){
				p=++tot;
				key[p]=x,cnt[p]=1;
			}
			else cnt[p]++;
		}
	}
	int getcount(ull x){
		int v=x%M;int p=head[v];
		while(p){
			if(key[p]==x)return cnt[p];
			p=nxt[p];
		}
		return 0;
	}
}Map;

void solve() {
  scanf("%s", s + 1), n = strlen(s + 1);
  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;
  Map.clear();
  for (int i = n; i; --i) {
    for (int j = i - 1; j; --j) f[j][i - 1] = Map.getcount(query(j, i - 1));
    for (int j = i; j <= n; ++j) Map.ins(query(i, j));
  }
  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);
}

int T;

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