#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+100;
char a[maxn],b[maxn];
int z[maxn],cnt[maxn];
string s;
void calc(int n) {
	int l=0,r=0;
	z[0]=n;
	for (int i=1;i<n;i++) {
		int x=0;
		if (i<=r) x=min(z[i-l],r-i);
		while (i+x<n&&b[x]==b[i+x]) x++;
		if (i+x-1>r) l=i,r=i+x-1;
		z[i]=x;
	}
}
int main() {
	int T;cin>>T;
	while (T--) {
		cin>>s;int n=s.size();ll ans=0;
		for (int st=1;st<n;st++) {
			int i=0;
			for (;st+i<n;i++) b[i]=s[st+i];
			b[i++]='#';
			for (int j=0;j<st;j++) b[i++]=s[j];
			calc(n+1);
			for (int i=1;i<=st;i++) {
				if (z[n+1-i]==i) cnt[i]=1;
			}
			for (int i=1;i<=n;i++) cnt[i]+=cnt[i-1];
			for (int i=1;i+st<n;i++) {
				int x=max(min(z[i]-1,i-2),0);
				ans+=cnt[x];
			}
			for (int i=1;i<=n;i++) cnt[i]=0;
		}
		cout<<ans<<endl;
	}
}