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;
inline long long Read() {
  long long s = 0, f = 1;
  char x;
  for (x = getchar(); x < '0' || x > '9'; x = getchar())
    if (x == '-') f = -1;
  for (; x >= '0' && x <= '9'; x = getchar()) s = (s * 10) + (x & 15);
  return f == 1 ? s : -s;
}
const long long A = 4e5 + 5;
long long T;
char a[A];
long long len;
long long las, sz;
struct SAM {
  long long len, f;
  long long nex[26];
} tr[A];
long long dp[A];
inline void build() {
  for (long long i = 0; i <= sz; i++) {
    dp[i] = 0;
    for (long long j = 0; j < 26; j++) tr[i].nex[j] = 0;
  }
  las = sz = 1;
  tr[1].len = 0, tr[1].f = 0;
  return;
}
inline void add(long long x) {
  long long cur = ++sz;
  tr[cur].len = tr[las].len + 1;
  long long p = las;
  while (p && !tr[p].nex[x]) {
    tr[p].nex[x] = cur;
    p = tr[p].f;
  }
  if (!p)
    tr[cur].f = 1;
  else {
    long long q = tr[p].nex[x];
    if (tr[p].len + 1 == tr[q].len)
      tr[cur].f = q;
    else {
      long long cn = ++sz;
      tr[cn] = tr[q];
      tr[cn].len = tr[p].len + 1;
      tr[cur].f = tr[q].f = cn;
      while (p && tr[p].nex[x] == q) {
        tr[p].nex[x] = cn;
        p = tr[p].f;
      }
    }
  }
  dp[cur] = 1;
  las = cur;
  return;
}
long long t[A], p[A];
inline void Sort() {
  for (long long i = 0; i <= sz; i++) t[i] = 0;
  for (long long i = 1; i <= sz; i++) t[tr[i].len]++;
  for (long long i = 1; i <= sz; i++) t[i] += t[i - 1];
  for (long long i = sz; i; i--) p[t[tr[i].len]--] = i;
  return;
}
signed main() {
  T = Read();
  while (T--) {
    scanf("%s", a + 1);
    len = strlen(a + 1);
    build();
    for (long long i = 1; i <= len; i++) add(a[i] - 'a');
    Sort();
    long long ans = 0;
    for (long long i = sz; i; i--) dp[tr[p[i]].f] += dp[p[i]];
    for (long long i = 1; i <= sz; i++)
      ans += ((tr[i].len - tr[tr[i].f].len) * dp[i] * dp[i]);
    printf("%lld\n", ans);
  }
  return 0;
}