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>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
template <class T, class U>
inline void Max(T &a, U b) {
  if (a < b) a = b;
}
template <class T, class U>
inline void Min(T &a, U b) {
  if (a > b) a = b;
}
inline void add(int &a, int b) {
  a += b;
  while (a >= 1000000007) a -= 1000000007;
}
int pow(int a, int b) {
  int ans = 1;
  while (b) {
    if (b & 1) ans = ans * (long long)a % 1000000007;
    a = (long long)a * a % 1000000007;
    b >>= 1;
  }
  return ans;
}
char s[200010];
struct node {
  int ch[26], v, fail, dep, f;
  void init() {
    memset(ch, 0, sizeof(ch));
    v = fail = dep = f = 0;
  }
} t[200010];
int sz, n;
void build(char s[]) {
  n = strlen(s);
  int ed = 0, p;
  sz = 0;
  t[0].init();
  t[0].fail = -1;
  for (int i = 0; i < n; i++) {
    int j = s[i] - 'a';
    p = ++sz;
    t[p].init();
    t[p].dep = t[ed].dep + 1;
    while (ed >= 0 && t[ed].ch[j] == 0) t[ed].ch[j] = p, ed = t[ed].fail;
    if (ed < 0) {
      ed = p;
      continue;
    }
    int q = t[ed].ch[j];
    if (t[q].dep == t[ed].dep + 1)
      t[p].fail = q;
    else {
      int r = ++sz;
      t[r] = t[q];
      t[r].dep = t[ed].dep + 1;
      t[r].f = 1;
      t[p].fail = t[q].fail = r;
      while (ed >= 0 && t[ed].ch[j] == q) t[ed].ch[j] = r, ed = t[ed].fail;
    }
    ed = p;
  }
}
int w[200010], id[200010];
long long sqr(int first) { return 1LL * first * first; }
long long run() {
  long long ans = 0;
  for (int i = 0; i < n + 1; i++) w[i] = 0;
  for (int i = 0; i < sz + 1; i++) w[t[i].dep]++;
  for (int i = 1; i < n + 1; i++) w[i] += w[i - 1];
  for (int i = sz + 1 - 1; i >= 0; i--) id[--w[t[i].dep]] = i;
  for (int K = sz + 1 - 1; K >= 1; K--) {
    int i = id[K], j = t[i].fail;
    if (!t[i].f) t[i].v++;
    if (j >= 0) t[j].v += t[i].v;
    ans += sqr(t[i].v) * (t[i].dep - t[j].dep);
  }
  return ans;
}
int main() {
  int T, i = 0, j, k, ca = 0, K, m;
  scanf("%d", &T);
  while (T--) {
    scanf("%s", s);
    build(s);
    long long ans = run();
    printf("%I64d\n", ans);
  }
  return 0;
}