Problem: Now that you have proposed a fake post for the HC2 Facebook page, Heidi wants to measure the quality of the post before actually posting it. She recently came across a (possibly fake) article about the impact of fractal structure on multimedia messages and she is now trying to measure the self-similarity of the message, which is defined as

<image>

where the sum is over all nonempty strings p and <image> is the number of occurences of p in s as a substring. (Note that the sum is infinite, but it only has a finite number of nonzero summands.)

Heidi refuses to do anything else until she knows how to calculate this self-similarity. Could you please help her? (If you would like to instead convince Heidi that a finite string cannot be a fractal anyway – do not bother, we have already tried.)

Input

The input starts with a line indicating the number of test cases T (1 ≤ T ≤ 10). After that, T test cases follow, each of which consists of one line containing a string s (1 ≤ |s| ≤ 100 000) composed of lowercase letters (a-z).

Output

Output T lines, every line containing one number – the answer to the corresponding test case.

Example

Input

4
aa
abcd
ccc
abcc


Output

5
10
14
12

Note

A string s contains another string p as a substring if p is a contiguous subsequence of s. For example, ab is a substring of cab but not of acb.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int N = 101010;
int n, k, t, sa[N], lcp[N], r[N], tmp[N], c[N], L[N], R[N];
string s;
bool suffCmp(int u, int v) {
  if (r[u] != r[v]) return r[u] < r[v];
  if (u + k < n && v + k < n) return r[u + k] < r[v + k];
  return (u > v);
}
void CountingSort(int k) {
  memset(c, 0, sizeof(c));
  for (int i = 0; i < n; i++) c[(i + k < n ? r[i + k] + 1 : 0)]++;
  for (int i = 1; i <= max(n, 256); i++) c[i] += c[i - 1];
  for (int i = n - 1; i >= 0; i--)
    tmp[--c[(sa[i] + k < n ? r[sa[i] + k] + 1 : 0)]] = sa[i];
  for (int i = 0; i < n; i++) sa[i] = tmp[i];
}
void makeSA() {
  for (int i = 0; i < n; i++) sa[i] = i, r[i] = s[i];
  for (k = 1; k < n; k <<= 1) {
    CountingSort(k);
    CountingSort(0);
    tmp[sa[0]] = 0;
    for (int i = 1; i < n; i++)
      tmp[sa[i]] = tmp[sa[i - 1]] + suffCmp(sa[i - 1], sa[i]);
    for (int i = 0; i < n; i++) r[i] = tmp[i];
    if (tmp[sa[n - 1]] == n - 1) break;
  }
}
void makeLCP() {
  for (int i = 0, k = 0; i < n; i++, k -= (k > 0))
    if (r[i] != n - 1) {
      int j = sa[r[i] + 1];
      while (i + k < n && j + k < n && s[i + k] == s[j + k]) k++;
      lcp[r[i]] = k;
    }
}
int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> t;
  while (t--) {
    cin >> s;
    n = s.size();
    makeSA();
    makeLCP();
    for (int i = 0; i < n; i++) {
      L[i] = i;
      int j = i - 1;
      while (j >= 0 && lcp[i] <= lcp[j]) L[i] = L[j], j = L[j] - 1;
    }
    for (int i = n - 1; i >= 0; i--) {
      R[i] = i;
      int j = i + 1;
      while (j < n && lcp[i] <= lcp[j]) R[i] = R[j], j = R[j] + 1;
    }
    long long sum = 0, preMatch = 0;
    for (int i = 0; i < n; i++) {
      int len = n - sa[i] - max(lcp[i], lcp[i - 1]);
      sum += len;
    }
    map<pair<int, int>, bool> vis;
    for (int i = 0; i < n; i++)
      if (vis.count(pair<int, int>(L[i], R[i])) == 0) {
        long long len = lcp[i] - max(lcp[L[i] - 1], lcp[R[i] + 1]);
        long long cnt = R[i] - L[i] + 2;
        sum += len * cnt * cnt;
        vis[pair<int, int>(L[i], R[i])] = 1;
      }
    cout << sum << "\n";
  }
  return 0;
}