#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=30005;
char str[N];
int n;
int rk[N*2],h[N],sa[N],rnk[N*2],now;
bool cmp(int x,int y){return rk[x]==rk[y]?(rk[x+now]<rk[y+now]):(rk[x]<rk[y]);}
void Sa(){
	for (int i=1;i<=n;++i)rk[i]=str[i],sa[i]=i;
	for (int j=1;j<n;j<<=1){
		now=j;sort(sa+1,sa+n+1,cmp);
		for (int i=1;i<=n;++i)rnk[i]=rk[i];
		int tot=0;
		for (int i=1;i<=n;++i){
			if (rnk[sa[i]]!=rnk[sa[i-1]]||rnk[sa[i]+now]!=rnk[sa[i-1]+now]||i==1)++tot;
			rk[sa[i]]=tot;
		}
	}
	for (int i=1,p=0;i<=n;++i){
		if (p)--p;
		while (str[i+p]==str[sa[rk[i]-1]+p]&&i+p<=n&&sa[rk[i]-1]+p<=n)++p;
		h[rk[i]]=p;
	}
}
int A[N],B[N],f[N],g[N];
struct BIT{
	int tr[N],top,st[N*3][2];
	void add(int x,int v,bool ck){
		if (!ck)st[++top][0]=x,st[top][1]=v;
		for (int i=x;i<=n;i+=(i&(-i)))tr[i]+=v;
	}
	int qry(int x){
		int s=0;
		for (int i=x;i;i-=(i&(-i)))s+=tr[i];
		return s;
	}
	int query(int x,int y){return x>y?0:(qry(y)-qry(x-1));}
	void del(){
		while (top)add(st[top][0],-st[top][1],1),--top;
	}
}T;
void solve1(int l,int r){
	if (l==r)return;
	int mid=(l+r)>>1;
	A[mid]=n+1;
	for (int i=mid-1;i>=l;--i)A[i]=min(A[i+1],h[i+1]);
	B[mid+1]=h[mid+1];
	for (int i=mid+2;i<=r;++i)B[i]=min(B[i-1],h[i]);
	int j=mid;
	for (int i=mid;i>=l;--i){
		while (A[i]<B[j+1]&&j+1<=r){
			++j;
			T.add(sa[j],1,0);
		}
		if (sa[i]^n)f[sa[i]]+=T.query(sa[i]+1,min(n,sa[i]+A[i]));
	}
	T.del();
	j=r+1;
	for (int i=l;i<=mid;++i){
		while (A[i]>=B[j-1]&&j-1>=mid+1){
			--j;
			if (sa[j]==1)continue;
			int u=sa[j]-B[j],v=sa[j]-1;
			if (u<=v){
				u=max(u,1);
				T.add(u,1,0),T.add(v+1,-1,0);
			}
		}
		f[sa[i]]+=T.qry(sa[i]);
	}
	T.del();
	solve1(l,mid),solve1(mid+1,r);
}
void solve2(int l,int r){
	if (l==r)return;
	int mid=(l+r)>>1;
	A[mid]=n+1;
	for (int i=mid-1;i>=l;--i)A[i]=min(A[i+1],h[i+1]);
	B[mid+1]=h[mid+1];
	for (int i=mid+2;i<=r;++i)B[i]=min(B[i-1],h[i]);
	int j=l-1;
	for (int i=r;i>=mid+1;--i){
		while (j+1<=mid&&A[j+1]<B[i]){
			++j;
			if (sa[j]==1)continue;
			int u=sa[j]-A[j],v=sa[j]-1;
			if (u<=v){
				u=max(u,1);
				T.add(u,1,0),T.add(v+1,-1,0);
			}
		}
		f[sa[i]]+=T.qry(sa[i]);
	}
	T.del();
	j=mid+1;
	for (int i=mid+1;i<=r;++i){
		while (j-1>=l&&A[j-1]>=B[i]){
			--j;
			T.add(sa[j],1,0);
		}
		if (sa[i]^n)f[sa[i]]+=T.query(sa[i]+1,min(sa[i]+B[i],n));
	}
	T.del();
	solve2(l,mid),solve2(mid+1,r);
}
void solve3(int l,int r){
	if (l==r)return;
	int mid=(l+r)>>1;
	A[mid]=n+1;
	for (int i=mid-1;i>=l;--i)A[i]=min(A[i+1],h[i+1]);
	B[mid+1]=h[mid+1];
	for (int i=mid+2;i<=r;++i)B[i]=min(B[i-1],h[i]);
	int j=mid;
	for (int i=mid;i>=l;--i){
		while (A[i]<B[j+1]&&j+1<=r){
			++j;
			T.add(sa[j],1,0);
		}
		if (sa[i]^n)g[sa[i]]+=T.query(sa[i]+1,min(n,sa[i]+A[i]));
	}
	T.del();
	j=r+1;
	for (int i=l;i<=mid;++i){
		while (A[i]>=B[j-1]&&j-1>=mid+1){
			--j;
			if (sa[j]==1)continue;
			int u=sa[j]-B[j],v=sa[j]-1;
			if (u<=v){
				u=max(u,1);
				T.add(u,1,0),T.add(v+1,-1,0);
			}
		}
		g[sa[i]]+=T.qry(sa[i]);
	}
	T.del();
	solve3(l,mid),solve3(mid+1,r);
}
void solve4(int l,int r){
	if (l==r)return;
	int mid=(l+r)>>1;
	A[mid]=n+1;
	for (int i=mid-1;i>=l;--i)A[i]=min(A[i+1],h[i+1]);
	B[mid+1]=h[mid+1];
	for (int i=mid+2;i<=r;++i)B[i]=min(B[i-1],h[i]);
	int j=l-1;
	for (int i=r;i>=mid+1;--i){
		while (j+1<=mid&&A[j+1]<B[i]){
			++j;
			if (sa[j]==1)continue;
			int u=sa[j]-A[j],v=sa[j]-1;
			if (u<=v){
				u=max(u,1);
				T.add(u,1,0),T.add(v+1,-1,0);
			}
		}
		g[sa[i]]+=T.qry(sa[i]);
	}
	T.del();
	j=mid+1;
	for (int i=mid+1;i<=r;++i){
		while (j-1>=l&&A[j-1]>=B[i]){
			--j;
			T.add(sa[j],1,0);
		}
		if (sa[i]^n)g[sa[i]]+=T.query(sa[i]+1,min(sa[i]+B[i],n));
	}
	T.del();
	solve4(l,mid),solve4(mid+1,r);
}
void solve(){
	scanf("%s",str+1);
	n=strlen(str+1);
	Sa();
	solve1(1,n);
	solve2(1,n);
	for (int i=1;i*2<=n;++i)swap(str[i],str[n-i+1]);
	for (int i=0;i<=2*n;++i)rk[i]=rnk[i]=0;
	Sa();
	solve3(1,n);
	solve4(1,n);
	ll ans=0;
	for (int i=1;i*2<=n;++i)swap(g[i],g[n-i+1]);
	for (int i=1;i<=n;++i)ans+=1ll*f[i]*g[i-1];
	for (int i=0;i<=n;++i)f[i]=g[i]=h[i]=0;
	for (int i=0;i<=2*n;++i)rk[i]=rnk[i]=0;
	printf("%lld\n",ans);
}
int main(){
	int T;
	scanf("%d",&T);
	while (T--)solve();
}