#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
pair<pair<int, int>, int> x[N];
int n, rnk[N], rev[N];
vector<int> pos[N];
set<int> st;
char s[N];
inline long long get(int x) { return 1LL * x * x; }
inline void set_rank() {
  sort(x, x + n);
  for (int i = 1, cur = 0; i < n; i++)
    rnk[x[i].second] = cur += x[i].first != x[i - 1].first;
}
inline void build_suffix_array() {
  for (int i = 0; i < n; i++) x[i] = {{s[i], rnk[i] = 0}, i};
  set_rank();
  for (int i = 0; n >> i; i++) {
    for (int j = 0; j < n; j++)
      x[j] = {{rnk[j], j + (1 << i) < n ? rnk[j + (1 << i)] : -1}, j};
    set_rank();
  }
}
inline void build_lcp_array() {
  for (int i = rnk[n] = n; ~i; i--) rev[rnk[i]] = i;
  for (int i = 0, cur = 0; i < n; i++) {
    while (s[i + cur] == s[rev[rnk[i] + 1] + cur]) cur++;
    if (cur) pos[cur--].push_back(rnk[i]);
  }
}
inline void read_input() {
  cin >> s;
  n = strlen(s);
}
inline void solve() {
  build_suffix_array();
  build_lcp_array();
}
inline void write_output() {
  long long ans = 0, cur = 0;
  for (int i = n; i; i--) st.insert(i);
  for (int i = n; i; i--) {
    for (auto p : pos[i]) {
      auto r = st.upper_bound(p), l = r++, mid = l--;
      cur -= get(*mid - *l) + get(*r - *mid);
      cur += get(*r - *l), st.erase(mid);
    }
    pos[i].clear(), ans += ++cur;
  }
  cout << ans << endl;
}
inline void test_cases() {
  int t;
  cin >> t;
  st.insert(0);
  while (t--) {
    read_input();
    solve();
    write_output();
  }
}
int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  test_cases();
  return 0;
}
