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>
#pragma comment(linker, "/STACK:160777216")
using namespace std;
int n, i, j, k;
const int MAXN = 1 << 21;
int N, gap;
int sa[MAXN], pos[MAXN], tmp[MAXN], lcp[MAXN];
bool sufCmp(int i, int j) {
  if (pos[i] != pos[j]) return pos[i] < pos[j];
  i += gap;
  j += gap;
  return (i < N && j < N) ? pos[i] < pos[j] : i > j;
}
void buildSA(string S) {
  N = S.size();
  for (int i = 0; i < (int)(N); ++i) sa[i] = i, pos[i] = S[i];
  for (gap = 1;; gap *= 2) {
    sort(sa, sa + N, sufCmp);
    for (int i = 0; i < (int)(N - 1); ++i)
      tmp[i + 1] = tmp[i] + sufCmp(sa[i], sa[i + 1]);
    for (int i = 0; i < (int)(N); ++i) pos[sa[i]] = tmp[i];
    if (tmp[N - 1] == N - 1) break;
  }
}
void buildLCP(string S) {
  for (int i = 0, k = 0; i < N; ++i)
    if (pos[i] != N - 1) {
      for (int j = sa[pos[i] + 1]; S[i + k] == S[j + k];) ++k;
      lcp[pos[i]] = k;
      if (k) --k;
    }
}
char tmps[200000];
struct str {
  int l, r;
  str() {}
  str(int _l, int _r) {
    l = _l;
    r = _r;
  }
  long long getlen() { return (long long)(r - l + 1) * (r - l + 1); }
};
bool operator<(str a, str b) { return a.l < b.l || a.l == b.l && a.r < b.r; }
vector<int> v[200000];
int nom[200000];
char tmp1[111111];
int main() {
  int tt;
  cin >> tt;
  gets(tmp1);
  while (tt--) {
    string s;
    gets(tmp1);
    s = tmp1;
    n = s.size();
    buildSA(s);
    buildLCP(s);
    long long ans = n;
    ans *= n;
    set<str> st;
    st.insert(str(0, n - 1));
    for (i = 0; i < n; i++) nom[sa[i]] = i;
    for (i = 0; i < n - 1; i++) {
      v[lcp[i]].push_back(i);
    }
    long long glans = 0;
    for (i = 0; i < n; i++) {
      for (j = 0; j < v[i].size(); j++) {
        set<str>::iterator it1 = st.lower_bound({v[i][j] + 1, 0});
        if (it1 == st.begin()) continue;
        it1--;
        str it = *it1;
        if (v[i][j] >= it.l && v[i][j] <= it.r)
          ;
        else
          continue;
        ans -= it.getlen();
        st.erase(it);
        str add1 = str(it.l, v[i][j]);
        str add2 = str(v[i][j] + 1, it.r);
        st.insert(add1);
        st.insert(add2);
        ans += add1.getlen() + add2.getlen();
      }
      glans += ans;
      set<str>::iterator it1 = st.lower_bound({nom[n - i - 1] + 1, 0});
      if (it1 != st.begin()) {
        it1--;
        str it = *it1;
        if (nom[n - i - 1] >= it.l && nom[n - i - 1] <= it.r)
          ;
        else
          continue;
        st.erase(it);
        ans -= it.getlen();
        str add1 = str(it.l, nom[n - i - 1] - 1);
        str add2 = str(nom[n - i - 1] + 1, it.r);
        if (add1.l <= add1.r) {
          st.insert(add1);
          ans += add1.getlen();
        }
        if (add2.l <= add2.r) {
          st.insert(add2);
          ans += add2.getlen();
        }
      }
    }
    for (i = 0; i < n - 1; i++) {
      v[lcp[i]].clear();
    }
    cout << glans << endl;
  }
  return 0;
}