#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
using namespace std;
int sum[26][1050000], len;
long long ans;
int check(string s, int st, int a, int b, int fa, int fc) {
	int res = (fa <= fc);
	string A = s.substr(0, a + 1);
	string B = s.substr(a + 1, b - a);
	if (st + b + b + 1 < len - 1 && s.substr(b + 1, b + 1) == A + B) {
		int F = 0;
		for (int j = 0; j < 26; j++) {
			F += (sum[j][len - 1] - sum[j][st + b + b + 1]) & 1;
		}
		res += check(s.substr(b + 1, len - b - 1), st + b + 1, a, b, fa, F);
	}
	return res;
}
int main() {
	freopen("string.in", "r", stdin);
	freopen("string.out", "w", stdout);
	int T; cin >> T;
	while (T--) {
		string s; cin >> s;
		len = s.length(); ans = 0;
		for (int j = 0; j < 26; j++) {
			sum[j][0] = (s[0] - 'a' == j);
		}
		for (int i = 1; i < len; i++) {
			for (int j = 0; j < 26; j++) {
				sum[j][i] = sum[j][i - 1] + (s[i] - 'a' == j);
			}
		}
		for (int i = 0; i < len - 2; i++) {
			for (int j = i + 1; j < len - 1; j++) {
				int F1 = 0, F2 = 0;
				for (int k = 0; k < 26; k++) {
					F1 += (sum[k][i] & 1);
					F2 += (sum[k][len - 1] - sum[k][j]) & 1;
				}
				ans += check(s, 0, i, j, F1, F2);
			}
		}
		cout << ans << endl;
	}
	return 0;
}