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;
class Node {
 public:
  int f;
  int l;
  int s[26];
  Node(void) : f(-1), l(0) {
    memset(s, 0, sizeof(s));
    return;
  }
};
char a[200020];
Node f[200020];
int c, d;
int g[200020], t[200020], v[200020];
inline int ID(char c) { return c - 97; }
void InitSAM(void) {
  c = 1;
  d = 0;
  return;
}
void InsertSAM(int k) {
  int b, p, q;
  p = d;
  f[d = c++].l = f[p].l + 1;
  g[d] = 1;
  for (; p != -1 && !f[p].s[k]; p = f[p].f) f[p].s[k] = d;
  if (p == -1)
    f[d].f = 0;
  else {
    q = f[p].s[k];
    if (f[q].l == f[p].l + 1)
      f[d].f = q;
    else {
      f[b = c++] = f[q];
      f[q].f = f[d].f = b;
      f[b].l = f[p].l + 1;
      for (; p != -1 && f[p].s[k] == q; p = f[p].f) f[p].s[k] = b;
    }
  }
  return;
}
int main(void) {
  int t;
  int i;
  long long o;
  scanf("%d", &t);
  while (t--) {
    for (i = 0; i < 200020; i++) {
      f[i] = Node();
      g[i] = ::t[i] = 0;
    }
    scanf("%s", a);
    InitSAM();
    for (i = 0; a[i]; i++) InsertSAM(ID(a[i]));
    for (i = 0; i < c; i++) ::t[f[i].l]++;
    for (i = 1; a[i - 1]; i++) ::t[i] += ::t[i - 1];
    for (i = c - 1; i > -1; i--) v[--::t[f[i].l]] = i;
    for (i = c - 1; i > 0; i--) g[f[v[i]].f] += g[v[i]];
    for (i = 1, o = 0; i < c; i++)
      o += (long long)g[i] * g[i] * (f[i].l - f[f[i].f].l);
    printf("%lld\n", o);
  }
  return 0;
}