显然，我们有一个极度粗暴的想法：直接枚举每个长度大于 $2$ 前缀作为 $AB$ 这个整体，然后暴力将其往后推，一边推一边算：预处理所有后缀出现奇数次字符的数量，用树状数组维护每个出现奇数次字符数量的前缀的个数，查询时前缀和即可。

至于推的话，用字符串哈希来判匹配从而判断继续后推，整体后推次数是 $\sum_{i=1}^{n}\frac{1}{i}=\Theta(n\log n)$，字符串哈希基础上的字符串匹配单次是常数时间复杂度。

总时间复杂度 $\Theta(n\log n\log \mid \sum \mid)$，$\mid \sum \mid=26$ 为字符集大小。

//written by Amekawa_kanade
#include<bits/stdc++.h>
using namespace std;
const int N=1<<21;
using ll=long long;
int pref[N],npcnt[27];
using ull=unsigned ll;
const ull _x=37;
ull hs1[N],xp[N];
void init_xp(int _n=(1<<20)+11)
{
	xp[0]=1;
	for(int i=1;i<=_n;++i) xp[i]=xp[i-1]*_x;
}
ull ghs(int l,int r)
{
	return hs1[r]-hs1[l-1]*xp[r-l+1];
}
void GHS(char *s,int _n)
{
	for(int i=1;i<=_n;++i) hs1[i]=hs1[i-1]*_x+(s[i]-'a');
}
int n,suff[N],sufcnt[27];char s[N];
ll ans=0;
struct BIT
{
	ll C[N];int _c;
	int lowbit(int x) {return x&-x;}
	void add(int x,ll v)
	{
		x+=1;
		while(x<=_c) C[x]+=v,x+=lowbit(x); 
	}
	ll sum(int x)
	{
		x+=1;
		ll ret=0;
		while(x>0) ret+=C[x],x-=lowbit(x);
		return ret;
	}
	void clear()
	{
		for(int i=1;i<=_c+1;++i) C[i]=0;
		_c=0;
	}
};
BIT tr;
void pre_progress()
{
	n=strlen(s+1);tr._c=n+2;
	GHS(s,n);
	for(int i=n;i>=1;--i)
	{
		int nc=s[i]-'a'+1;
		if(sufcnt[nc]&1)
		{
			suff[i]=suff[i+1]-1;
			++sufcnt[nc];
		}
		else
		{
			suff[i]=suff[i+1]+1;
			++sufcnt[nc];
		}
	}
}
void solve()
{
	scanf("%s",s+1);
	pre_progress();
	ans=0;
	for(int len=1;len<=n-1;++len)
	{
		if(len>=2)
		{
			int cst=1+len;//printf("%d %lld:\n",len,ans);
			ans+=tr.sum(suff[cst]);//,printf("%d %d %lld \n",cst,suff[cst],ans);
			while(cst+len<=n&&ghs(1,len)==ghs(cst,cst+len-1)) cst+=len,ans+=tr.sum(suff[cst]);//,printf("%d %d %lld \n",cst,suff[cst],ans);
			//printf("%d %lld\n",len,ans);
		}
		int nc=s[len]-'a'+1;
		if(npcnt[nc]&1) pref[len]=pref[len-1]-1,tr.add(pref[len],1);
		else tr.add(pref[len-1]+1,1),pref[len]=pref[len-1]+1;
		++npcnt[nc];
	}
	printf("%lld\n",ans);hs1[0]=0;
	tr.clear();for(int i=0;i<=n;++i) pref[i]=suff[i]=0;
	for(int i=0;i<=26;++i) npcnt[i]=sufcnt[i]=0;
}
int t;
int main()
{
	init_xp();
	scanf("%d",&t);
	while(t--) solve();
	return 0;
}