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 MN = 1e5 + 10, LG = 18;
pair<pair<int, int>, int> T[MN];
int P[LG][MN], p[MN], rev[MN], lcp[MN], n;
string s;
void Ok(int i) {
  for (int j = 0; j < n; ++j)
    P[i][T[j].second] =
        j && T[j].first == T[j - 1].first ? P[i][T[j - 1].second] : j;
}
void prep() {
  for (int i = 0; i < n; ++i) T[i] = {{s[i], s[i]}, i};
  sort(T, T + n);
  Ok(0);
  for (int i = 1; i < LG; ++i) {
    for (int j = 0; j < n; ++j)
      T[j] = {{P[i - 1][j],
               j + (1 << (i - 1)) < n ? P[i - 1][j + (1 << (i - 1))] : -1},
              j};
    sort(T, T + n);
    Ok(i);
  }
  for (int i = 0; i < n; ++i) p[i] = P[LG - 1][i], rev[p[i]] = i;
  int pnt = 0;
  for (int i = 0; i < n; ++i) {
    pnt = max(pnt, 0);
    if (p[i] == n - 1)
      pnt = 0;
    else {
      int x = rev[p[i] + 1];
      while (max(x, i) + pnt < n && s[i + pnt] == s[x + pnt]) ++pnt;
    }
    lcp[p[i]] = pnt--;
  }
}
int main() {
  ios_base ::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  int Tst;
  cin >> Tst;
  while (Tst--) {
    cin >> s;
    n = ((int)(s).size());
    prep();
    set<int> S = {-1, n - 1};
    set<int>::iterator it;
    long long ans = 0;
    for (int i = 0; i < n; ++i) T[i] = {{lcp[i], 0}, i};
    sort(T, T + n);
    for (int i = 0; i < n; ++i) {
      int id = T[i].second;
      it = S.upper_bound(id);
      int x = *it - id;
      --it;
      int y = id - *it;
      S.insert(id);
      ans += 1ll * x * y * T[i].first.first;
    }
    cout << 2 * ans + 1ll * n * (n + 1) / 2 << '\n';
  }
  return 0;
}