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>
const int Maxn = 1e5 + 5;
template <typename Temp>
inline void read(Temp& res) {
  Temp fh = 1;
  res = 0;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') fh = -1;
  for (; isdigit(ch); ch = getchar())
    res = (res << 3) + (res << 1) + (ch ^ '0');
  res = res * fh;
}
int tr[Maxn << 1][26], link[Maxn << 1], len[Maxn << 1], id[Maxn << 1],
    rk[Maxn << 1];
long long size[Maxn << 1], cnt, last;
void extend(int c) {
  int cur = ++cnt, p = last;
  len[cur] = len[last] + 1;
  last = cur;
  size[cur] = 1;
  while (p && !tr[p][c]) tr[p][c] = cur, p = link[p];
  if (!p) {
    link[cur] = 1;
    return;
  }
  int q = tr[p][c];
  if (len[q] == len[p] + 1) {
    link[cur] = q;
    return;
  }
  int cl = ++cnt;
  len[cl] = len[p] + 1;
  memcpy(tr[cl], tr[q], sizeof(tr[cl]));
  link[cl] = link[q];
  link[cur] = link[q] = cl;
  while (p && tr[p][c] == q) tr[p][c] = cl, p = link[p];
}
void forsize() {
  for (int i = 1; i <= cnt; ++i) ++rk[len[i]];
  for (int i = 1; i <= cnt; ++i) rk[i] += rk[i - 1];
  for (int i = cnt; i >= 1; --i) id[rk[len[i]]--] = i;
  for (int i = cnt; i >= 1; --i) size[link[id[i]]] += size[id[i]];
}
int T, k;
char s[Maxn];
int main() {
  read(T);
  while (T--) {
    scanf("%s", s + 1);
    int n = strlen(s + 1);
    last = cnt = 1;
    for (int i = 1; i < 2 * n; ++i)
      link[i] = size[i] = len[i] = rk[i] = id[i] = 0,
      memset(tr[i], 0, sizeof(tr[i]));
    for (int i = 1; i <= n; ++i) extend(s[i] - 'a');
    long long ans = 0;
    forsize();
    for (int i = 1; i <= cnt; ++i) {
      ans = ans + 1ll * size[i] * size[i] * (len[i] - len[link[i]]);
    }
    printf("%lld\n", ans);
  }
  return 0;
}