#include<cstdio>
#include<cstring>
#include<algorithm>
#define ull unsigned long long
using namespace std;
char s[1100005];
ull hashe[1100005],p[1100005],ans;
int qti[205],hti[205],qjs[1100005],hjs[1100005],t,n,c[1100005][31];
void add(int x,int y)
{
	for(int i=x;i<=n;i+=(i&-i))
		for(int j=y;j<=30;j+=(j&-j))
			c[i][j]++;
	return;
}
ull ask(int x,int y)
{
	ull k=0;
	for(int i=x;i;i-=(i&-i))
		for(int j=y;j;j-=(j&-j))
			k+=c[i][j];
	return k;
}
int main()
{
	p[0]=1;
	for(int i=1;i<=1100000;i++) p[i]=p[i-1]*13331;
	scanf("%d",&t);
	while(t--)
	{
		ans=0;
		memset(qti,0,sizeof(qti));
		memset(hti,0,sizeof(hti));
		for(int i=1;i<=n;i++) 
		{
			qjs[i]=hjs[i]=0;
			for(int j=1;j<='z'-'a'+1;j++) c[i][j]=0;
		}
		scanf("%s",s+1);
		n=strlen(s+1);
		for(int i=1;i<=n;i++)
		{
			qti[s[i]]++;hti[s[n-i+1]]++;
			if(qti[s[i]]%2) qjs[i]=qjs[i-1]+1;
			else qjs[i]=qjs[i-1]-1;
			if(hti[s[n-i+1]]%2) hjs[n-i+1]=hjs[n-i+2]+1;
			else hjs[n-i+1]=hjs[n-i+2]-1;
			add(i,qjs[i]+1);
		}
		for(int i=1;i<=n;i++) hashe[i]=hashe[i-1]*13331+(ull)(s[i]-'a');
		for(int i=2;i<n;i++)
		{
			int l=1,r=(n-1)/i,mid;
			while(l<r)
			{
				mid=(l+r+1)>>1;
				//printf("%d %d %d %d\n",i,l,r,mid);
				if(hashe[(mid-1)*i]*p[i]==hashe[mid*i]-hashe[i]) l=mid;
				else r=mid-1;
			}
			//printf("%d\n",l);
			//while(l*i>=n || hashe[(l-1)*i]*p[i]!=hashe[l*i]-hashe[i]) l--;
			//printf("%d %d\n",i,l);
			ans+=(l+1)/2*ask(i-1,hjs[i*l+1]+1)+l/2*ask(i-1,hjs[i*(l-1)+1]+1);
		}
		printf("%lld\n",ans);
	}
	return 0;
}