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 double eps = 1e-9;
const int inf = 2e9;
const double pi = acos(-1.0);
long long read() {
  long long x = 0, f = 1;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * f;
}
int l[400500], val[400500], fa[400500], head[400500], c[400500][26];
int n, last, tot, idx;
long long ans;
char s[400500], gg[400500];
struct data {
  int obj, pre;
} e[400500 * 2];
void add(int x) {
  int p = last, np, q, nq;
  np = ++tot;
  l[np] = l[p] + 1;
  while (p && !c[p][x]) c[p][x] = np, p = fa[p];
  if (!p)
    fa[np] = 1;
  else {
    q = c[p][x];
    if (l[q] == l[p] + 1)
      fa[np] = q;
    else {
      nq = ++tot;
      l[nq] = l[p] + 1;
      for (int j = 0; j <= 25; j++) c[nq][j] = c[q][j];
      fa[nq] = fa[q];
      fa[q] = fa[np] = nq;
      for (; c[p][x] == q; p = fa[p]) c[p][x] = nq;
    }
  }
  last = np;
  val[np]++;
}
void insert(int x, int y) {
  e[++idx].obj = y;
  e[idx].pre = head[x];
  head[x] = idx;
}
void dfs(int u) {
  for (int j = head[u]; j; j = e[j].pre) {
    int v = e[j].obj;
    dfs(v);
    val[u] += val[v];
  }
  ans += 1ll * (l[u] - l[fa[u]]) * val[u] * val[u];
}
int main() {
  int _ = read();
  while (_--) {
    tot = last = 1;
    idx = 0;
    scanf("%s", s + 1);
    int n = strlen(s + 1);
    for (int i = 1; i <= n; i++) add(s[i] - 'a');
    for (int i = 1; i <= tot; i++) insert(fa[i], i);
    ans = 0;
    dfs(1);
    printf("%lld\n", ans);
    for (int i = 1; i <= tot; i++)
      fa[i] = l[i] = val[i] = 0, memset(c[i], 0, sizeof(c[i]));
    for (int i = 1; i <= idx; i++) head[i] = 0;
  }
  return 0;
}