#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int mod = 1e9 + 9;

const int N = 5e3;
const int B = 131;

int n;
char s[N + 5];
int pw[N + 5], h[N + 5];
int f[N + 5][N + 5];
unordered_map<int, int> cnt;
int query(int l, int r) { return (h[r] + (ll)(mod - pw[r - l + 1]) * h[l - 1]) % mod; }
ll ans;

void solve() {
  scanf("%s", s + 1), n = strlen(s + 1);
  pw[0] = 1;
  for (int i = 1; i <= n; ++i) pw[i] = (ll)pw[i - 1] * B % mod;
  for (int i = 1; i <= n; ++i) h[i] = ((ll)h[i - 1] * B + s[i] - '0' + 1) % mod;
  cnt.clear();
  for (int i = n; i; --i) {
    for (int j = i - 1; j; --j) f[j][i - 1] = cnt[query(j, i - 1)];
    for (int j = i; j <= n; ++j) ++cnt[query(i, j)];
  }
  ans = 0;
  for (int i = 1; i <= n; ++i) {
    int cur = 0;
    for (int len = 1; i + len - 1 <= n; ++len) {
      ans += (ll)cur * f[i][i + len - 1];
      if (len <= i - 1 && query(i - len, i - 1) == query(i, i + len - 1)) ++cur;
    }
  }
  printf("%d\n", ans);
}

int T;

int main() {
  for (scanf("%d", &T); T; --T) solve();
}