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;
const int N = 100010;
const int M = 1e9 + 7;
template <class T>
inline T read(T &x) {
  int f = 1;
  char ch = getchar();
  x = 0;
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x *= f;
}
int T, n;
char str[N];
int sa[N], rk[N], _rk[N], cnt[N], id[N], ht[N];
int Cmp(int x, int y, int w) {
  return _rk[x] == _rk[y] && _rk[x + w] == _rk[y + w];
}
void SA() {
  int m = 30, p;
  memset(cnt, 0, sizeof(cnt));
  for (int(i) = (1); (i) <= (n); (i)++) cnt[rk[i] = str[i] - 'a' + 1]++;
  for (int(i) = (1); (i) <= (m); (i)++) cnt[i] += cnt[i - 1];
  for (int(i) = (n); (i) >= (1); (i)--) sa[cnt[rk[i]]--] = i;
  for (int w = 1; w < n; w *= 2, m = p) {
    p = 0;
    for (int(i) = (n - w + 1); (i) <= (n); (i)++) id[++p] = i;
    for (int(i) = (1); (i) <= (n); (i)++)
      if (sa[i] > w) id[++p] = sa[i] - w;
    memset(cnt, 0, sizeof(cnt));
    for (int(i) = (1); (i) <= (n); (i)++) cnt[rk[id[i]]]++;
    for (int(i) = (1); (i) <= (m); (i)++) cnt[i] += cnt[i - 1];
    for (int(i) = (n); (i) >= (1); (i)--) sa[cnt[rk[id[i]]]--] = id[i];
    p = 0;
    memcpy(_rk, rk, sizeof(_rk));
    for (int(i) = (1); (i) <= (n); (i)++)
      rk[sa[i]] = Cmp(sa[i], sa[i - 1], w) ? p : ++p;
  }
  p = 0;
  for (int(i) = (1); (i) <= (n); (i)++) {
    if (p) p--;
    while (str[i + p] == str[sa[rk[i] - 1] + p]) p++;
    ht[rk[i]] = p;
  }
}
struct Stack {
  int h, len;
} stk[N];
int top;
long long ans, sum;
int main() {
  read(T);
  while (T--) {
    scanf("%s\n", str + 1);
    n = strlen(str + 1);
    SA();
    ans = 1ll * n * (n + 1) / 2;
    sum = top = 0;
    for (int(i) = (2); (i) <= (n); (i)++) {
      Stack tmp = (Stack){ht[i], 1};
      while (top && ht[i] < stk[top].h) {
        sum -= 1ll * stk[top].h * stk[top].len;
        tmp.len += stk[top].len;
        top--;
      }
      stk[++top] = tmp;
      sum += 1ll * tmp.h * tmp.len;
      ans += sum * 2;
    }
    printf("%lld\n", ans);
  }
  return 0;
}