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;
int t, Num_Edge, head[200001];
long long ret, siz[200001];
char s[200001];
struct Edge {
  int v, nxt;
} E[300001];
void Add_Edge(int u, int v) {
  E[++Num_Edge].v = v;
  E[Num_Edge].nxt = head[u];
  head[u] = Num_Edge;
}
struct SAM {
  int tot = 1, pre = 1, fa[200001], v[200001], tr[200001][51];
  void Clear() {
    tot = pre = 1;
    memset(fa, 0, sizeof(fa));
    memset(v, 0, sizeof(v));
    memset(tr, 0, sizeof(tr));
  }
  void Ins(int x) {
    int now = ++tot, t = pre;
    pre = now;
    v[now] = v[t] + 1;
    siz[now] = 1;
    while (t && !tr[t][x]) {
      tr[t][x] = now;
      t = fa[t];
    }
    if (!t)
      fa[now] = 1;
    else if (v[tr[t][x]] == v[t] + 1)
      fa[now] = tr[t][x];
    else {
      int nv = ++tot, pv = tr[t][x];
      fa[nv] = fa[pv];
      v[nv] = v[t] + 1;
      for (int i = 0; i < 26; i++) tr[nv][i] = tr[pv][i];
      while (t && tr[t][x] == pv) {
        tr[t][x] = nv;
        t = fa[t];
      }
      fa[now] = fa[pv] = nv;
    }
  }
} T;
void DFS(int x) {
  for (int i = head[x]; i; i = E[i].nxt) {
    DFS(E[i].v);
    siz[x] += siz[E[i].v];
  }
  ret += siz[x] * siz[x] * (T.v[x] - T.v[T.fa[x]]);
}
int main() {
  scanf("%d", &t);
  while (t--) {
    T.Clear();
    ret = Num_Edge = 0;
    memset(E, 0, sizeof(E));
    memset(siz, 0, sizeof(siz));
    memset(head, 0, sizeof(head));
    scanf("%s", s);
    int n = strlen(s);
    for (int i = 0; i < n; i++) T.Ins(s[i] - 'a');
    for (int i = 2; i <= T.tot; i++) Add_Edge(T.fa[i], i);
    DFS(1);
    printf("%lld\n", ret);
  }
  return 0;
}