#include <bits/stdc++.h>
#define endl '\n'
#define maxl 1050000
#define ull unsigned long long
using namespace std;
char s[maxl];
ull h[maxl], p[maxl] = {1}, ans;
int len, cnt[26], tot[maxl], tree[27];
ull get(const int &l, const int &r) {
	if (l > r) return 0;
	return h[r] - h[l - 1] * p[r - l + 1];
}
void add(int x) {
	x++;
	while (x <= 26) {
		tree[x]++;
		x += x & -x;
	}
}
int query(int x) {
	x++;
	int res = 0;
	while (x) {
		res += tree[x];
		x &= x - 1;
	}
	return res;
}
bool f(const int &x, const int &y) {
	if (get(1, y - x) != get(x + 1, y))
		return 1;
	ans += query(tot[y + 1]);
	return 0;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t, x;
	for (int i = 1; i < maxl; i++)
		p[i] = p[i - 1] * 27;
	scanf("%d",&t);
	while (t--) {
		memset(tree, 0, sizeof(tree));
		scanf("%s",s+1);
		len = strlen(s + 1);
		for (int i = 1; i <= len; i++) {
			s[i] -= 'a';
			h[i] = h[i - 1] * 27 + s[i];
		}
		memset(cnt, 0, sizeof(cnt));
		x = 0;
		for (int i = len; i; i--) {
			if (++cnt[s[i]] & 1)
				x++;
			else x--;
			tot[i] = x;
		}
		memset(cnt, 0, sizeof(cnt));
		ans = 0;
		x = cnt[s[1]] = 1;
		for (int i = 2; i <= len; i++) {
			add(x);
			cnt[s[i]]++;
			if (cnt[s[i]] & 1) x++;
			else x--;
			for (int j = i; j < len; j += i)
				if (f(i, j)) break;
		}
		cout << ans << endl;
	}
}