#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10, inf = 0x3f3f3f3f;
int sa[N];
int rk[N];
int tmp[N];
int lcp[N];
char s[N], t[N];
int n, k;
bool cmp(int i, int j) {
  if (rk[i] != rk[j])
    return rk[i] < rk[j];
  else {
    int ri = i + k <= n ? rk[i + k] : -1;
    int rj = j + k <= n ? rk[j + k] : -1;
    return ri < rj;
  }
}
void build(char *s, int *sa) {
  n = strlen(s);
  for (int i = 0; i <= n; i++) {
    sa[i] = i;
    rk[i] = i < n ? s[i] : -1;
  }
  for (k = 1; k <= n; k *= 2) {
    sort(sa, sa + n + 1, cmp);
    tmp[sa[0]] = 0;
    for (int i = 1; i <= n; i++) {
      tmp[sa[i]] = tmp[sa[i - 1]] + (cmp(sa[i - 1], sa[i]) ? 1 : 0);
    }
    for (int i = 0; i <= n; i++) {
      rk[i] = tmp[i];
    }
  }
}
void LCP(char *s, int *sa, int *lcp) {
  n = strlen(s);
  for (int i = 0; i <= n; i++) rk[sa[i]] = i;
  int h = 0;
  lcp[0] = 0;
  for (int i = 0; i < n; i++) {
    int j = sa[rk[i] - 1];
    for (h ? h-- : 0; j + h < n && i + h < n && s[j + h] == s[i + h]; h++)
      ;
    lcp[rk[i] - 1] = h;
  }
}
int st[N], pos[N];
int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    scanf("%s", s);
    int n = strlen(s);
    build(s, sa);
    LCP(s, sa, lcp);
    for (int i = 0; i < n; i++) {
    }
    int now = 0;
    lcp[n] = 0;
    long long ans = 0;
    for (int i = 1; i <= n; i++) {
      int newpos = i, len = lcp[i];
      while (now > 0 && st[now] > len) {
        long long v1 = st[now] - max(st[now - 1], len);
        long long v2 = i - pos[now] + 1;
        ans += v1 * v2 * v2;
        newpos = pos[now--];
      }
      st[++now] = len;
      pos[now] = newpos;
    }
    for (int i = 0; i < n; i++) {
      ans += n - i - max(lcp[rk[i] - 1], lcp[rk[i]]);
    }
    printf("%lld\n", ans);
  }
  return 0;
}
