#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int MAXN = (1<<20) + 5;

#define bbit(i) (1<<(i))
#define bdig(x,i) (((x)>>(i))&1)
#define lowbit(x) ((x)&-(x))

const int all = (1<<20) - 1, ALL = all + 5;
int num1[ALL];
inline int get_num1(int x){ return num1[x&all] + num1[x>>20];}

template<const int N>
struct BIT// range [0, N]
{
	int MAXN;
	BIT(void): MAXN(N+2) {}
	int tree[N+2];
	inline void clear(void){ memset(tree,0,sizeof(tree));}
	inline void update(int x,int k)
	{
		++x;
		while(x<MAXN)
			tree[x] += k,
			x += lowbit(x);
	}
	inline int query(int x)
	{
		++x;
		int res = 0;
		while(x)
			res += tree[x],
			x ^= lowbit(x);
		return res;
	}
};

int n;
char s[MAXN];

int z[MAXN];
void get_z(void)
{
	z[1] = n;
	for(int i=2,l=1,r=1; i<=n; ++i)
	{
		z[i] = i<r? min(r-i, z[1+i-l]): 0;
		while(s[1+z[i]] == s[i+z[i]]) ++z[i];
		if(i+z[i] > r) l=i, r=i+z[i];
	}
}

int pre[MAXN], suf[MAXN];

void solve(void)
{
	scanf("%s",s+1);
	n = strlen(s+1);
	
	get_z();
	
	pre[0] = 0;
	for(int i=1; i<=n; ++i) pre[i] = pre[i-1] ^ bbit(s[i] - 'a');
	suf[n+1] = 0;
	for(int i=n; i>=1; --i) suf[i] = suf[i+1] ^ bbit(s[i] - 'a');
	
	static BIT<26> tree;
	tree.clear();
	
	ll ans = 0;
	for(int i=1; i<n; ++i)
	{
		if(i==1){ tree.update(get_num1(pre[i]), 1); continue;}
		
		int cnt = min(z[i+1], n-i-1) / i, rb = i + cnt * i;
		
		int type1 = get_num1(suf[rb+1]), c1 = (cnt>>1) + (rb < n);
		int type2 = get_num1(suf[rb+1] ^ pre[i]), c2 = (cnt+1)>>1;
		
		ans += (ll)tree.query(type1) * c1 + (ll)tree.query(type2) * c2;
		
		tree.update(get_num1(pre[i]), 1);
	}
	printf("%lld\n",ans);
}

int main(void)
{
//	freopen("string.in","r",stdin);
//	freopen("string.out","w",stdout);
	
	num1[0] = 0;
	for(int i=1; i<ALL; ++i) num1[i] = num1[i^lowbit(i)] + 1;
	
	int T;
	scanf("%d",&T);
	while(T--) solve();
	return 0;
}