#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 100;
int num;
int sa[N], fir[N], sec[N], t[N];
int height[N], L[N], R[N], st[N];
char c[N];
inline long long SA(int len, char s[]) {
  num = 300;
  for (int i = 1; i <= num; i++) t[i] = 0;
  for (int i = 1; i <= len; i++) ++t[fir[i] = s[i]];
  for (int i = 1; i <= num; i++) t[i] += t[i - 1];
  for (int i = len; i >= 1; i--) sa[t[fir[i]]--] = i;
  for (int k = 1; k <= len; k <<= 1) {
    int cnt = 0;
    for (int i = len - k + 1; i <= len; i++) sec[++cnt] = i;
    for (int i = 1; i <= len; i++)
      if (sa[i] > k) sec[++cnt] = sa[i] - k;
    for (int i = 1; i <= num; i++) t[i] = 0;
    for (int i = 1; i <= len; i++) ++t[fir[i]];
    for (int i = 1; i <= num; i++) t[i] += t[i - 1];
    for (int i = len; i >= 1; i--) sa[t[fir[sec[i]]]--] = sec[i], sec[i] = 0;
    swap(fir, sec);
    fir[sa[1]] = 1, cnt = 1;
    for (int i = 2; i <= len; i++)
      fir[sa[i]] =
          (sec[sa[i]] == sec[sa[i - 1]] && sec[sa[i] + k] == sec[sa[i - 1] + k])
              ? cnt
              : ++cnt;
    if (cnt == len) break;
    num = cnt;
  }
  int j, k = 0;
  for (int i = 1; i <= len; i++) {
    if (k) k--;
    int j = sa[fir[i] - 1];
    while (i + k <= len && j + k <= len && s[i + k] == s[j + k]) k++;
    height[fir[i]] = k;
  }
  int top = 1;
  st[top] = 1;
  for (int i = 2; i <= len; i++) {
    while (top && height[i] < height[st[top]]) R[st[top--]] = i;
    L[i] = st[top];
    st[++top] = i;
  }
  while (top) R[st[top--]] = len + 1;
  long long ans = 1ll * len * (len + 1) / 2ll;
  for (int i = 2; i <= len; i++) {
    ans += 2ll * height[i] * (R[i] - i) * (i - L[i]);
  }
  return ans;
}
int main() {
  int t;
  scanf("%d", &t);
  while (t--) {
    scanf("%s", c + 1);
    printf("%lld\n", SA(strlen(c + 1), c));
  }
  return 0;
}
