#include <iostream>
#include <map>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
 
const int MAXN = 1000000;
const long long BASE1 = 1000003;
const long long BASE2 = 239;
const long long MOD1 = 1000000007;
const long long MOD2 = 1000000009;
 
long long sha1[MAXN], sha2[MAXN], pw1[MAXN], pw2[MAXN], answer;
int f[MAXN], an, r_odd[MAXN], r_even[MAXN], ii, p[MAXN], t[MAXN], parent[MAXN], dp[MAXN], weight[MAXN];
bool created[MAXN];
int i, l, r, k, n, Tn;
char s[MAXN];
pair<long long, long long> a[MAXN];
map<pair<long long, long long>, int > palindromeness;
 
void init () {
	for(int i = 0; i <= n; i++) {
		sha1[i] = sha2[i] = pw1[i] = pw2[i] = 0;
		f[i] = r_odd[i] = r_even[i] = p[i] = t[i] = parent[i] = dp[i] = weight[i] = 0;
		created[i] = 0;
	}
	palindromeness.clear();
	answer = 0;
	an = ii = 0;	
}
 
pair<long long,long long>gethash(int j, int x){
    return make_pair(((sha1[j] - sha1[j + x] + MOD1) * pw1[j]) % MOD1, ((sha2[j] - sha2[j + x] + MOD2) * pw2[j]) % MOD2);
}
 
void get_palindromeness (int l, int r) {
	int left = l;
	int right = r;
	pair<long long, long long> final_hash = gethash(l, r - l + 1);
	int res = 1;
	while (l < r) {
		int h = (r - l + 1) / 2;
		if (gethash(l, h) == gethash(r - h + 1, h)) {
			++res;
			r = l + h - 1;
		} else break;
	}
	palindromeness[final_hash] = res;
}
 
void process_odd (){	
    for(i = 0, l = 0, r = -1; i < n; i++){
		k = (i > r ? 0 : min(f[l + r - i], r - i)) + 1;
		while(i + k < n && i - k >= 0 && s[i + k] == s[i - k]){
			a[++an] = gethash(i - k, 2 * k + 1);
			get_palindromeness(i - k, i + k);
			++k;
		}
		while (i + k >= n || i - k < 0 || s[i + k] != s[i - k]) --k;
		f[i] = k;
		a[++an] = gethash(i - k, 2 * k + 1);
		get_palindromeness(i - k, i + k);
		a[++an] = gethash(i, 1);
		get_palindromeness(i, i);
		if(i + k > r) {
			l = i - k;
			r = i + k;
		}
    }
	for(int i = 0; i < n; i++) r_odd[i] = f[i];
}
 
void process_even (){
    for(i = 0; i < n; i++) f[i] = 0;
    for(i = 0, l = 0, r = -1; i < n; i++){
		k = (i > r ? 0 : min(f[l + r - i + 1], r - i + 1)) + 1;
		while(i + k - 1 < n && i - k >= 0 && s[i - k] == s[i + k - 1]){
			a[++an] = gethash(i - k, 2 * k);
			get_palindromeness(i - k, i + k - 1);
			++k;
		}
		f[i] = --k;
		if(i + k - 1 > r) {
			l = i - k;
			r = i + k - 1;
		}
    }
	for(int i = 0; i < n; i++) {
		r_even[i] = f[i];
		f[i] = 0;
	}
}
 
void hash_init(){
    pw1[0] = pw2[0] = 1;
    for(i = 1; i <= n; i++) {
		pw1[i] = (pw1[i - 1] * BASE1) % MOD1;
		pw2[i] = (pw2[i - 1] * BASE2) % MOD2;
	}
    sha1[n - 1] = sha2[n - 1] = s[n - 1];
    for(i = n - 2; i >= 0; i--){
		sha1[i] = (sha1[i + 1] + pw1[n - i - 1] * s[i]) % MOD1;
		sha2[i] = (sha2[i + 1] + pw2[n - i - 1] * s[i]) % MOD2;
    }
}
 
int get_node_index (int l, int r) {
	pair<long long, long long> hash = gethash(l, r - l + 1);
	return lower_bound(a + 1, a + an + 1, hash) - a;
}
 
void add_edge (int x, int y) {
	t[++ii] = y;
	p[ii] = f[x];
	f[x] = ii;
}
 
void solve_odd () {
	for(int i = 0; i < n; i++) {
		int l = i - r_odd[i];
		int r = i + r_odd[i];
		while (!created[get_node_index(l, r)] && l < r) {
			created[get_node_index(l, r)] = true;
			parent[get_node_index(l, r)] = get_node_index(l + 1, r - 1);
			add_edge(get_node_index(l + 1, r - 1), get_node_index(l, r));			
			++l;
			--r;
		}
		if (!created[get_node_index(l, r)]) {
			created[get_node_index(l, r)] = true;
			parent[get_node_index(l, r)] = -1;
		}
	}
	for(int i = 0; i < n; i++) ++weight[get_node_index(i - r_odd[i], i + r_odd[i])];
}
 
void solve_even () {
	for(int i = 0; i < n; i++) if (r_even[i] != 0) {
		int l = i - r_even[i];
		int r = i + r_even[i] - 1;
		while (!created[get_node_index(l, r)] && l + 1 < r) {
			created[get_node_index(l, r)] = true;
			parent[get_node_index(l, r)] = get_node_index(l + 1, r - 1);
			add_edge(get_node_index(l + 1, r - 1), get_node_index(l, r));
			++l;
			--r;
		}
		if (!created[get_node_index(l, r)]) {
			created[get_node_index(l, r)] = true;
			parent[get_node_index(l, r)] = -1;
		}		
	}
	for(int i = 0; i < n; i++) if (r_even[i] != 0) {
		++weight[get_node_index(i - r_even[i], i + r_even[i] - 1)];		
	}
}
 
int dfs (int k) {
	int q = f[k];
	dp[k] = weight[k];
	while (q > 0) {
		dp[k] += dfs(t[q]);
		q = p[q];
	}
	return dp[k];
}
 
int main (int argc, char * const argv[]) {
	scanf("%d", &Tn);
	gets(s);
	while (Tn--) {
		init();
		gets(s);
		n = strlen(s);
		hash_init();
		process_odd();
		process_even();
		sort(a + 1, a + an + 1);
		an = unique(a + 1, a + an + 1) - (a + 1);
		solve_even();
		solve_odd();
		for(int i = 1; i <= an; i++) if (parent[i] == -1)
			dfs(i);
		for(int i = 1; i <= an; i++)
			answer += palindromeness[a[i]] * 1LL * dp[i];
		printf("%lld\n", answer);
	}
    return 0;
}