#include <cstdio>
#include <cstring>
#include <algorithm>
#include <utility>

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;

const int MAXL = 200001;

char a[MAXL];
int rad[MAXL], dbl[MAXL], tree[MAXL];
PII js[MAXL];

void manacher(int n) {
  LL tot = 0;

  for (int i = 0; i < n; ++i) dbl[i] = 0;

  for (int i = 0, j = 0, k; i < n; i += k) {
    while (i-j >= 0 && i+j < n && a[i-j] == a[i+j]) ++j;
    --j;

    rad[i] = j;
    k = 1;
    for (; k <= rad[i] && rad[i-k] != rad[i]-k; ++k)
      rad[i+k] = min(rad[i-k],rad[i]-k);

    j=max(j-k,0);
  }
}

void increase(int n, int k) {
  for (; k < n; k |= k+1) ++tree[k];
}

int query(int n, int k) {
  int s = 0;
  for (k = min(k,n-1); k >= 0; k = (k&(k+1))-1) s += tree[k];
  return s;
}

LL cnt(int n) {
  int nn = (n+1)/2;

  for (int j = 0; j < n; j += 2)
    js[j>>1] = PII((j<<1)-rad[j],j);
  sort(js,js+nn);

  LL tot = 0;
  memset(tree, 0, sizeof(tree));

  for (int i = 0, at = 0; i < n; i += 2) {
    while (at < nn && js[at].first <= (i<<1))
      increase(n, js[at++].second);
    tot += query(n, i+rad[i])-query(n,i);
  }
  return tot;
}

int main() {
  int t;
  scanf("%d", &t);
  while (t--) {
    scanf("%s", a);
    int n = strlen(a);

    for (int i = n-1; i >= 0; --i) {
      a[(i<<1)|1] = a[i];
      a[i<<1] = '#';
    }
    n = 2*n+1;
    a[n-1] = '#';
    a[n] = 0;

    manacher(n);
    printf("%lld\n", cnt(n));
  }
}