#include <iostream>
#include <cstdio>
#include <cstring>

#define ll long long

using namespace std;

const ll _MOD = 1000000007;

char _str[0x10000f];
int _length;
ll _hash[0x10000f];
int _preji[0x10000f];
int _lastji[0x10000f];
int _countji[128];
ll _count[0x10000f];
ll _res;

void Hash() {
  _hash[0] = _str[0]-'a';
  ll pow = 29;
  for (int i = 1; i < _length; i++) {
    _hash[i] = (_hash[i-1]+(_str[i]-'a')*pow)%_MOD;
    pow = pow*29%_MOD;
  }
}

void CountJi() {
  for (char i = 'a'; i <= 'z'; i++) {
    _countji[i] = 0;
  }
  for (int i = 0; i < _length; i++) {
    _countji[_str[i]]++;
    if (_countji[_str[i]]&1) {
      _preji[i] = _preji[i-1]+1;
      continue;
    }
    _preji[i] = _preji[i-1]-1;
  }
  for (char i = 'a'; i <= 'z'; i++) {
    _countji[i] = 0;
  }
  for (int i = _length-1; i > -1; i--) {
    _countji[_str[i]]++;
    if (_countji[_str[i]]&1) {
      _lastji[i] = _lastji[i+1]+1;
      continue;
    }
    _lastji[i] = _lastji[i+1]-1;
  }
  
}

void Push(int a, ll v) {
  //cout << "Push " << a << ',' << v << endl;
  while (a <= _length) {
    _count[a]+=v;
    a+=a&-a;
  }
}

ll Pre(int a) {
  ll res = 0;
  while (a) {
    res+=_count[a];
    a-=a&-a;
  }
  return res;
}

bool Nmsl(int len, int dis, int starti, int endi) {
  //cout << len << ',' << dis << ',' << starti << ',' << endi << endl;
  //cout << _hash[len-1]*dis%_MOD << ',' << (_hash[endi]-_hash[starti-1]+_MOD)%_MOD << endl;
  return _hash[len-1]*dis%_MOD!=(_hash[endi]-_hash[starti-1]+_MOD)%_MOD;
}

void Solve() {
  _res = 0;
  _length = strlen(_str);
  Hash();
  memset(_count, 0, sizeof(_count));
  //cout << _hash[2]*29*29*29%_MOD << ' ' << (_hash[5]-_hash[2])%_MOD << endl;
  CountJi();
  ll dis = 29*29;
  ll diss;
  for (int len = 2; len < _length; len++) {
    diss = 1;
    Push(_preji[len-2]+1, 1ll);
    for (int cnt = 1;; cnt++) {
      //cout << len << ',' << cnt << endl;
      //cout << _lastji[cnt*len]+1 << ',' << Pre(_lastji[cnt*len]+1) << endl;
      _res+=Pre(_lastji[cnt*len]+1);
      diss = diss*dis%_MOD;
      if ((cnt+1)*len >= _length || Nmsl(len, diss, cnt*len, (cnt+1)*len-1)) break;
    }
    dis = dis*29%_MOD;
  }
  printf("%lld\n", _res);
}

int main() {
  int t;
  freopen("string.in", "r", stdin);
  freopen("string.out", "w", stdout);
  scanf("%d", &t);
  while (t--) {
    scanf("%s", _str);
    Solve();
  }
  fclose(stdin);
  fclose(stdout);
  return 0;
}

改了一下洛谷直接96oitiku直接AC