#include<bits/stdc++.h>
#define int ll
#define up(i,l,r) for(int i=l,END##i=r;i<=END##i;i++)
#define dn(i,l,r) for(int i=l,END##i=r;i>=END##i;i--)
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
using namespace std;
const int INF=0x3f3f3f3f,N=1<<20;
ll n,all,lst,now,tot[30],cnt[30],z[N];
string s;
struct node {
	int c[30|1];
	void add(int x,int y) {
		while(x<=26) c[x]+=y,x|=x+1;
	}
	int sum(int x) {
		ll ans=0;
		while(x>=0) ans+=c[x],x&=x+1,x--;
		return ans;
	}
} T;
namespace sol {
	ll read() {
		ll f=0,x=0;
		char c=getchar();
		while(c<'0'||c>'9') f|=c=='-',c=getchar();
		while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
		return f?-x:x;
	}
	void write(ll x) {
		if(x<0) putchar('-'),x=-x;
		if(x>9) write(x/10);
		putchar(x%10+'0');
	}
	void get(string s) {
		ll l=0;
		up(i,0,n-1) z[i]=0;
		up(i,0,(ll)s.length()-1) {
		    if(!i) continue;
			if(l+z[l]>i) z[i]=min(z[i-l],l+z[l]-i);
			while(i+z[i]<n&&s[z[i]]==s[i+z[i]]) z[i]++;
			if(i+z[i]>l+z[l]) l=i;
		}
	}
	void fnnqaq() {
		cin>>s;
		n=s.length();
		get(s);
		up(i,0,n-1) if(i+z[i]==n) z[i]--;
		ll ans=all=lst=now=0;
		up(i,0,25) tot[i]=cnt[i]=T.c[i]=0;
		up(i,0,n-1) tot[s[i]-'a']++;
		up(i,0,25) all+=(tot[i]&1);
		lst=all;
		up(i,0,n-1) {
			tot[s[i]-'a']&1?lst--:lst++;
			cnt[s[i]-'a']&1?now--:now++;
			tot[s[i]-'a']--,cnt[s[i]-'a']++;
			if(i&&i<n-1) {
				ll fnn=z[i+1]/(i+1)+1;
				ans+=(fnn>>1)*T.sum(all)+(fnn-(fnn>>1))*T.sum(lst);
			}
		//	cout<<"now="<<now<<" last="<<lst<<" all="<<all<<'\n';
			T.add(now,1);
		}
		write(ans);
	}
}
using namespace sol;
signed main() {
	ll t=read();
	while(t--)
		fnnqaq(),puts("");
	return 0;
}