#include<bits/stdc++.h>
using namespace std;
const int N=5005;
int T,n,bu[N],lg[N];
char s[N];
namespace SA{
	int sa[N],rk[N],id[N],bu[N],p,st[17][N];
	void ss(){
		memset(sa,0,sizeof sa);
		memset(rk,0,sizeof rk);
		memset(id,0,sizeof id);
		memset(bu,0,sizeof bu);
		memset(st,0,sizeof st),p=0;
		for(int i=1;i<=n;++i) ++bu[s[i]];
		for(int i=1;i<='9';++i) bu[i]+=bu[i-1];
		for(int i=n;i;--i) sa[bu[s[i]]--]=i;
		for(int i=1;i<=n;++i) rk[sa[i]]=s[sa[i]]==s[sa[i-1]]?p:++p;
		for(int i=1;p<n;i*=2){
			for(int j=1;j<=p;++j) bu[j]=0;
			for(int j=1;j<=i;++j) id[j]=n-i+j;
			for(int j=1,k=i;j<=n;++j) if(sa[j]>i) id[++k]=sa[j]-i;
			for(int j=1;j<=n;++j) ++bu[rk[j]];
			for(int j=1;j<=p;++j) bu[j]+=bu[j-1];
			for(int j=n;j;--j) sa[bu[rk[id[j]]]--]=id[j],id[j]=rk[j];
			p=0;
			for(int j=1;j<=n;++j) rk[sa[j]]=id[sa[j]]==id[sa[j-1]]&&id[sa[j]+i]==id[sa[j-1]+i]?p:++p;
		}
		for(int i=1,k=0;i<=n;++i){
			k-=!!k;
			if(sa[i]>1) while(s[i+k]==s[sa[rk[i]-1]+k]) ++k;
			st[0][rk[i]]=k;
		}
		for(int i=1,p=2;p<=n;++i,p*=2)
			for(int j=1;j+p-1<=n;++j)
				st[i][j]=min(st[i-1][j],st[i-1][j+p/2]);
	}
	int lcp(int x,int y){
		if(x==y) return n-x+1;
		if((x=rk[x])>(y=rk[y])) swap(x,y);
		int t=lg[y-(++x)+1];
		return min(st[t][x],st[t][y-(1<<t)+1]);
	}
}
using SA::lcp;
long long ans;
void solve(){
	memset(s,0,sizeof s),scanf("%s",s+1),n=strlen(s+1),SA::ss();
	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;
	}
//	for(int i=1;i<=n;++i,puts(""))
//		for(int j=1;j<=n;++j)
//			printf("%d ",lcp(i,j));
	printf("%lld\n",ans),ans=0;
}
int main(){
	//freopen("A.in","r",stdin);
	//freopen("B2.out","w",stdout);
	for(int i=1;i<N;++i) lg[i]=lg[i-1]+(2<<lg[i-1]==i);
	scanf("%d",&T);
	while(T--) solve();
	return 0;
}