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 = 2e5 + 10, inf = 0x3f3f3f3f;
int sa[N];
int rk[N];
int tmp[N];
int lcp[N];
char s[N], t[N];
int n, k;
bool cmp(int i, int j) {
  if (rk[i] != rk[j])
    return rk[i] < rk[j];
  else {
    int ri = i + k <= n ? rk[i + k] : -1;
    int rj = j + k <= n ? rk[j + k] : -1;
    return ri < rj;
  }
}
void build(char *s, int *sa) {
  n = strlen(s);
  for (int i = 0; i <= n; i++) {
    sa[i] = i;
    rk[i] = i < n ? s[i] : -1;
  }
  for (k = 1; k <= n; k *= 2) {
    sort(sa, sa + n + 1, cmp);
    tmp[sa[0]] = 0;
    for (int i = 1; i <= n; i++) {
      tmp[sa[i]] = tmp[sa[i - 1]] + (cmp(sa[i - 1], sa[i]) ? 1 : 0);
    }
    for (int i = 0; i <= n; i++) {
      rk[i] = tmp[i];
    }
  }
}
void LCP(char *s, int *sa, int *lcp) {
  n = strlen(s);
  for (int i = 0; i <= n; i++) rk[sa[i]] = i;
  int h = 0;
  lcp[0] = 0;
  for (int i = 0; i < n; i++) {
    int j = sa[rk[i] - 1];
    for (h ? h-- : 0; j + h < n && i + h < n && s[j + h] == s[i + h]; h++)
      ;
    lcp[rk[i] - 1] = h;
  }
}
int st[N], pos[N];
int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    scanf("%s", s);
    int n = strlen(s);
    build(s, sa);
    LCP(s, sa, lcp);
    for (int i = 0; i < n; i++) {
    }
    int now = 0;
    lcp[n] = 0;
    long long ans = 0;
    for (int i = 1; i <= n; i++) {
      int newpos = i, len = lcp[i];
      while (now > 0 && st[now] > len) {
        long long v1 = st[now] - max(st[now - 1], len);
        long long v2 = i - pos[now] + 1;
        ans += v1 * v2 * v2;
        newpos = pos[now--];
      }
      st[++now] = len;
      pos[now] = newpos;
    }
    for (int i = 0; i < n; i++) {
      ans += n - i - max(lcp[rk[i] - 1], lcp[rk[i]]);
    }
    printf("%lld\n", ans);
  }
  return 0;
}