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 = 1e5 + 100;
int num;
int sa[N], fir[N], sec[N], t[N];
int height[N], L[N], R[N], st[N];
char c[N];
inline long long SA(int len, char s[]) {
  num = 300;
  for (int i = 1; i <= num; i++) t[i] = 0;
  for (int i = 1; i <= len; i++) ++t[fir[i] = s[i]];
  for (int i = 1; i <= num; i++) t[i] += t[i - 1];
  for (int i = len; i >= 1; i--) sa[t[fir[i]]--] = i;
  for (int k = 1; k <= len; k <<= 1) {
    int cnt = 0;
    for (int i = len - k + 1; i <= len; i++) sec[++cnt] = i;
    for (int i = 1; i <= len; i++)
      if (sa[i] > k) sec[++cnt] = sa[i] - k;
    for (int i = 1; i <= num; i++) t[i] = 0;
    for (int i = 1; i <= len; i++) ++t[fir[i]];
    for (int i = 1; i <= num; i++) t[i] += t[i - 1];
    for (int i = len; i >= 1; i--) sa[t[fir[sec[i]]]--] = sec[i], sec[i] = 0;
    swap(fir, sec);
    fir[sa[1]] = 1, cnt = 1;
    for (int i = 2; i <= len; i++)
      fir[sa[i]] =
          (sec[sa[i]] == sec[sa[i - 1]] && sec[sa[i] + k] == sec[sa[i - 1] + k])
              ? cnt
              : ++cnt;
    if (cnt == len) break;
    num = cnt;
  }
  int j, k = 0;
  for (int i = 1; i <= len; i++) {
    if (k) k--;
    int j = sa[fir[i] - 1];
    while (i + k <= len && j + k <= len && s[i + k] == s[j + k]) k++;
    height[fir[i]] = k;
  }
  int top = 1;
  st[top] = 1;
  for (int i = 2; i <= len; i++) {
    while (top && height[i] < height[st[top]]) R[st[top--]] = i;
    L[i] = st[top];
    st[++top] = i;
  }
  while (top) R[st[top--]] = len + 1;
  long long ans = 1ll * len * (len + 1) / 2ll;
  for (int i = 2; i <= len; i++) {
    ans += 2ll * height[i] * (R[i] - i) * (i - L[i]);
  }
  return ans;
}
int main() {
  int t;
  scanf("%d", &t);
  while (t--) {
    scanf("%s", c + 1);
    printf("%lld\n", SA(strlen(c + 1), c));
  }
  return 0;
}