#include<bits/stdc++.h>
using namespace std;
const int base=1e5+7;
const int N=(1<<20)+5;
unsigned long long h[N],m[N];
unsigned long long gethash(int l,int r){
	return h[r]-h[l-1]*m[r-l+1];
}
int pre[N][26],suf[N][26];
int p[N],s[N];
int tree[30];
int lowbit(int x){
	return x&-x;
}
void add(int x,int pos){
	while(pos<=27){
		tree[pos]+=x;
		pos+=lowbit(pos);
	}
}
long long getsum(int pos){
	long long ans=0;
	while(pos>0){
		ans+=tree[pos];
		pos-=lowbit(pos);
	}
	return ans;
}
void solve(){
	long long ans=0;
	string s;cin>>s;
	int n=s.size();
	s=' '+s;
	
	m[0]=1;
	for(int i=1;i<=n;i++){
		h[i]=h[i-1]*base+s[i]-'a'+1;
		m[i]=m[i-1]*base;
	}
	
	for(int i=1;i<=n;i++){
		for(int c=0;c<26;c++) pre[i][c]=pre[i-1][c];
		pre[i][s[i]-'a']++;
		if(pre[i][s[i]-'a']%2) p[i]=p[i-1]+1;
		else p[i]=p[i-1]-1;
	}
	
	for(int i=n;i>=1;i--){
		for(int c=0;c<26;c++) suf[i][c]=suf[i+1][c]; 
		suf[i][s[i]-'a']++;
		if(suf[i][s[i]-'a']%2) s[i]=s[i+1]+1;
		else s[i]=s[i+1]-1;
	} 
	//枚举AB长度 
	for(int i=2;i<n;i++){
		int r=i;
		unsigned long long hval=h[i];
		add(1,p[i-1]+1);
		for(;;){
			ans+=getsum(s[r+1]+1);
			if(r+i>=n||gethash(r+1,r+i)!=hval) break;
			r+=i;
		}
	}
	cout<<ans<<endl;
	for(int i=1;i<=n;i++) for(int c=0;c<26;c++) pre[i][c]=suf[i][c]=0;
	memset(tree,0,sizeof(tree));
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int t;cin>>t;
	while(t--) solve();
	return 0;
}