#include <bits/stdc++.h>
using namespace std;
char buf[100010];
string s;
int N;
int sa[100010 + 10], sainv[100010 + 10], lcp[100010 + 10];
pair<pair<int, int>, int> p[100010 + 10], q[100010 + 10];
void suffix_array(void) {
  int i, j, tmp = 0;
  for ((i) = 0; (i) < (int)(N); (i)++) sainv[i] = s[i];
  for (int t = 1; t < N; t *= 2) {
    for ((i) = 0; (i) < (int)(N); (i)++)
      p[i] =
          make_pair(make_pair(sainv[i], ((i + t >= N) ? -1 : sainv[i + t])), i);
    sort(p, p + N);
    int sz = 0;
    for ((i) = 0; (i) < (int)(N); (i)++) {
      if (i > 0 && p[i].first != p[i - 1].first) sz++;
      sainv[p[i].second] = sz;
    }
  }
  for ((i) = 0; (i) < (int)(N); (i)++) sa[sainv[i]] = i;
  for ((i) = 0; (i) < (int)(N); (i)++)
    if (sainv[i] != N - 1) {
      j = sa[sainv[i] + 1];
      while (i + tmp < N && j + tmp < N && s[i + tmp] == s[j + tmp]) tmp++;
      lcp[sainv[i]] = tmp;
      if (tmp > 0) tmp--;
    }
}
long long main2(void) {
  int i, j, k;
  long long ans = 0;
  set<int> sep;
  sep.insert(0);
  sep.insert(N);
  vector<pair<int, int> > v;
  for ((i) = 0; (i) < (int)(N - 1); (i)++)
    v.push_back(make_pair(lcp[i], i + 1));
  sort(v.begin(), v.end());
  for ((i) = 0; (i) < (int)(v.size()); (i)++) {
    int x = v[i].second;
    long long val = v[i].first;
    sep.insert(x);
    __typeof(sep.begin()) itr = sep.find(x);
    itr--;
    int L = *(itr);
    itr++;
    itr++;
    int R = *(itr);
    ans += val * (x - L) * (R - x);
  }
  ans = 2 * ans;
  for (i = 1; i <= N; i++) ans += i;
  return ans;
}
int main(void) {
  int T, t;
  cin >> T;
  for ((t) = 0; (t) < (int)(T); (t)++) {
    scanf("%s", buf);
    s = buf;
    N = s.length();
    suffix_array();
    long long ans = main2();
    cout << ans << endl;
  }
  return 0;
}
