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 long long N = 2e5 + 5;
struct node {
  long long x, w;
} v[N];
long long T, t, mm[N], front[N], beh[N], p[N];
char s[N];
bool o[N];
long long find_1_(long long x) {
  if (x == front[x]) return x;
  return front[x] = find_1_(front[x]);
}
long long find_2_(long long x) {
  if (x == beh[x]) return x;
  return beh[x] = find_2_(beh[x]);
}
bool cmp(node a, node b) {
  if (a.w != b.w)
    return a.w > b.w;
  else
    return a.x < b.x;
}
struct SA {
  char s[N];
  long long n, m, id[N], cnt[N], rk[N], sa[N], height[N];
  void build() {
    m = 300;
    memset(id, 0, sizeof(id));
    memset(cnt, 0, sizeof(cnt));
    memset(rk, 0, sizeof(rk));
    memset(sa, 0, sizeof(sa));
    memset(height, 0, sizeof(height));
    for (long long i = 1; i <= n; i++) cnt[rk[i] = s[i]]++;
    for (long long i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
    for (long long i = n; i >= 1; i--) sa[cnt[rk[i]]--] = i;
    for (long long w = 1; w <= n; w *= 2) {
      long long p = 0;
      for (long long i = 0; i <= m; i++) id[i] = 0;
      for (long long i = n - w + 1; i <= n; i++) id[++p] = i;
      for (long long i = 1; i <= n; i++) {
        if (sa[i] > w) id[++p] = sa[i] - w;
      }
      for (long long i = 0; i <= m; i++) cnt[i] = 0;
      for (long long i = 1; i <= n; i++) cnt[rk[id[i]]]++;
      for (long long i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
      for (long long i = n; i >= 1; i--) sa[cnt[rk[id[i]]]--] = id[i];
      swap(rk, id);
      rk[sa[1]] = p = 1;
      for (long long i = 2; i <= n; i++)
        rk[sa[i]] =
            (id[sa[i]] == id[sa[i - 1]] && id[sa[i] + w] == id[sa[i - 1] + w])
                ? p
                : ++p;
      if (p >= n) break;
      m = p;
    }
    long long k = 0;
    for (long long i = 1; i <= n; i++) rk[sa[i]] = i;
    for (long long i = 1; i <= n; i++) {
      if (rk[i] == 1) continue;
      if (k) k--;
      long long j = sa[rk[i] - 1];
      while (i + k <= n && j + k <= n && s[i + k] == s[j + k]) k++;
      height[rk[i]] = k;
    }
  }
} a;
signed main() {
  scanf("%lld", &T);
  while (T--) {
    memset(mm, 0, sizeof(mm));
    memset(p, false, sizeof(p));
    memset(o, false, sizeof(o));
    scanf("%s", s + 1);
    a.n = strlen(s + 1);
    long long ans = 0;
    t = 0;
    for (long long i = 1; i <= a.n; i++) a.s[i] = s[i];
    a.build();
    for (long long i = 1; i <= a.n; i++) front[i] = beh[i] = i;
    mm[1] = a.height[2];
    mm[a.n] = a.height[a.n];
    for (long long i = 2; i < a.n; i++)
      mm[i] = max(a.height[i], a.height[i + 1]);
    for (long long i = 1; i <= a.n; i++) ans += a.n - a.sa[i] + 1 - mm[i];
    long long bbbb = 56854656, mp = 0;
    for (long long i = 2; i <= a.n; i++) {
      if (a.height[i] != a.height[i - 1]) {
        v[++t] = (node){i, a.height[i]};
        if (a.height[i] > mp) {
          mp = a.height[i];
          bbbb = i;
        } else if (a.height[i] == mp)
          bbbb = min(bbbb, i);
      }
    }
    sort(v + 1, v + t + 1, cmp);
    for (long long i = 1; i <= t; i++) {
      long long be = v[i].x, en = v[i].x;
      while (a.height[find_1_(en) + 1] >= v[i].w && find_1_(en) < a.n)
        en = find_1_(en) + 1;
      while (a.height[find_2_(be) - 1] >= v[i].w && find_2_(be) > 1)
        be = find_2_(be) - 1;
      en = find_1_(en);
      be = find_2_(be);
      if (p[en] == v[i].w) continue;
      ans += (v[i].w - max(a.height[en + 1], a.height[be - 1])) *
             (en - be + 2) * (en - be + 2);
      front[be] = en;
      beh[en] = be;
      p[en] = v[i].w;
    }
    printf("%lld\n", ans);
  }
}