#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <queue>
#include <bitset>

using namespace std;
using ll = long long;
const int N = 5e3 + 5;

int n;
char s[N];
int lcp[N][N];
int sum[N][N];

void init() {
  for (int i = 0; i < n; i++) {
    fill(sum[i], sum[i] + n + 1, 0);
    fill(lcp[i], lcp[i] + n, 0);    
  }

  for (int i = n; i--; ) {
    for (int j = n; j--;) {
      if (s[i] == s[j]) lcp[i][j] = lcp[i+1][j+1] + 1;
    }
  }

}

inline int get_sum(int i, int l, int r) {
  return sum[i][r] - sum[i][l-1];
}

void solve() {
  cin >> s; 
  n = strlen(s);
  init();

  for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
      int p = min(lcp[i][j], j-i-1);
      if (p) {
        sum[i][1]++;
        sum[i][p+1]--;
      }
    }

    for (int j = 1; j <= n; j++) {
      sum[i][j] += sum[i][j-1];
    }

    for (int j = 1; j <= n; j++) {
      sum[i][j] += sum[i][j-1];
    }
  }

  int cnt = 0;
  for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
      if (lcp[i][j] < j - i) continue;
      int a = j - i;
      cnt += get_sum(j, a + 1, n); 
    }
  }
  
  printf("%d\n", cnt);
}

int main() {
  ios::sync_with_stdio(false); cin.tie(0);

  int t; cin >> t; while (t--)
    solve();

  return 0;  
}