#include<bits/stdc++.h>
using namespace std;
const int N=5005;
int T,n,bu[N],lg[N];
char s[N];
namespace SA{
	int x[N],y[N],c[N],sa[N],rk[N],h[N],st[N][19];
	inline void get_sa(){
		memset(x,0,sizeof(x));
		memset(y,0,sizeof(y));
		memset(sa,0,sizeof(sa));
		memset(h,0,sizeof(h));
		memset(rk,0,sizeof(rk));
		memset(st,0,sizeof(st));
		memset(c,0,sizeof(c));
		int m=300;
		for(int i=1;i<=n;i++) c[x[i]=s[i]]++;
		for(int i=1;i<=m;i++) c[i]+=c[i-1];
		for(int i=n;i;i--) sa[c[x[i]]--]=i;
		for(int k=1;k<=n;k<<=1){
			int num=0;
			for(int i=n-k+1;i<=n;i++) y[++num]=i;
			for(int i=1;i<=n;i++)
				if(sa[i]>k) y[++num]=sa[i]-k;
			for(int i=1;i<=m;i++) c[i]=0;
			for(int i=1;i<=n;i++) c[x[y[i]]]++;
			for(int i=1;i<=m;i++) c[i]+=c[i-1];
			for(int i=n;i;i--) sa[c[x[y[i]]]--]=y[i],y[i]=0;
			swap(x,y);
			x[sa[1]]=num=1;
			for(int i=2;i<=n;i++)
				x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])?num:++num;
			if(n==num) break;
			m=num;
		}
		for(int i=1;i<=n;i++) rk[sa[i]]=i;
		for(int i=1,k=0;i<=n;i++){
			if(rk[i]==1) continue;
			if(k) k--;
			while(i+k<=n&&sa[rk[i]-1]+k<=n&&s[i+k]==s[sa[rk[i]-1]+k]) k++;  
			h[rk[i]]=k;
		}
		for(int i=1;i<=n;i++) st[i][0]=h[i];
		for(int j=1;j<=lg[n];j++)
			for(int i=1;(i+(1<<j)-1)<=n;i++)
				st[i][j]=min(st[i][j-1],st[i+(1<<j-1)][j-1]);
	}
	inline int lcp(int x,int y){
		if(x==y) return n-x+1;
		x=rk[x],y=rk[y];
		if(x>y) swap(x,y);
		x++;
		int k=lg[y-x+1];
		return min(st[x][k],st[y-(1<<k)+1][k]);
	}
}
using SA::lcp;
long long ans;
void solve(){
	scanf("%s",s+1),n=strlen(s+1),SA::get_sa();
	for(int i=1;i<=n;++i){
		for(int j=i+2;j<=n;++j)
			++bu[min(j-i-1,lcp(i,j))];
		for(int j=n;j;--j) bu[j-1]+=bu[j];
		for(int j=1;j<i;++j)
			if(lcp(j,i)>=i-j)
				ans+=bu[i-j+1];
		for(int j=0;j<=n;++j) bu[j]=0;
	}
	printf("%lld\n",ans),ans=0;
}
int main(){
	for(int i=2;i<N;i++) lg[i]=lg[i>>1]+1;
	scanf("%d",&T);
	while(T--) solve();
	return 0;
}