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>
struct StackElement {
  int t;
  int val;
};
long long int solve();
char string[100001];
int text[100001];
int length;
int main() {
  std::ios::sync_with_stdio(false);
  int tests;
  std::cin >> tests;
  std::cin.ignore(1, '\n');
  for (int i = 0; i < tests; i++) {
    std::cin.getline(string, 100001);
    length = strlen(string) + 1;
    std::cout << solve() << '\n';
  }
}
void convertAscii() {
  for (int i = 0; i < length; i++) {
    if (string[i] == 0)
      text[i] = 0;
    else
      text[i] = string[i] - 'a' + 1;
  }
}
int prepareBuckets(int *index, int *start) {
  int used[27] = {0};
  for (int i = 0; i < length; i++) used[text[i]]++;
  int buckets = 0;
  for (int i = 0; i < 27; i++)
    if (used[i]) buckets++;
  {
    int use = 0;
    int st = 0;
    for (int i = 0; i < length; i++) {
      if (used[use] == 0) {
        used[use++] = st;
        st = i;
        while (used[use] == 0) use++;
      }
      start[i] = st;
      used[use]--;
    }
    used[use++] = st;
  }
  for (int i = 0; i < length; i++) {
    index[used[text[i]]] = i;
    used[text[i]]++;
  }
  return buckets;
}
void createSuffixArray(int *index) {
  int *original = index;
  convertAscii();
  int *data = new int[length * 5];
  int *nindex = data;
  int *start = data + length;
  int *lookup = data + 2 * length;
  int *cause = data + 3 * length;
  int *offset = data + 4 * length;
  int buckets = prepareBuckets(index, start);
  int s = 1;
  while (buckets != length) {
    for (int i = 0; i < length; i++) {
      lookup[index[i]] = i;
      offset[i] = 0;
    }
    for (int i = 0; i < length; i++) {
      int mov = index[i] - s;
      if (mov < 0) mov += length;
      int pos = lookup[mov];
      int npos = start[pos] + offset[start[pos]]++;
      nindex[npos] = mov;
      cause[npos] = start[i];
    }
    buckets = 1;
    int lstart = start[0];
    int nstart = 0;
    for (int i = 1; i < length; i++) {
      if (start[i] == lstart) {
        if (cause[i] != cause[i - 1]) {
          nstart = i;
          buckets++;
        }
      } else {
        nstart = i;
        buckets++;
      }
      lstart = start[i];
      start[i] = nstart;
    }
    int *temp = nindex;
    nindex = index;
    index = temp;
    s <<= 1;
  }
  if (original != index)
    for (int i = 0; i < length; i++) original[i] = index[i];
  delete[] data;
}
long long int solve() {
  int *index = new int[length];
  createSuffixArray(index);
  long long int sum = 0;
  {
    int *lcp = new int[2 * length];
    int *lookup = lcp + length;
    for (int i = 0; i < length; i++) lookup[index[i]] = i;
    int k = 0;
    for (int i = 0; i < length; i++) {
      if (lookup[i] == length - 1) {
        k = 0;
        continue;
      }
      int j = index[lookup[i] + 1];
      while (i + k < length && j + k < length && string[i + k] == string[j + k])
        k++;
      lcp[lookup[i]] = k;
      if (k > 0) k--;
    }
    StackElement *stack = new StackElement[length - 2];
    int p = 0;
    int current = 0;
    int lastLCP = 0;
    for (int i = 1; i < length - 1; i++) {
      int val = lcp[i];
      sum += (length - 1 - index[i]) - (lastLCP > val ? lastLCP : val);
      int dif = val - current;
      while (p > 0 && (dif + stack[p - 1].val) < 0) {
        long long int s = (i - stack[p - 1].t + 1);
        sum += stack[p - 1].val * s * s;
        dif += stack[p - 1].val;
        current -= stack[p - 1].val;
        p--;
      }
      int t = i;
      if (dif < 0) {
        long long int s = (i - stack[p - 1].t + 1);
        sum += (-dif) * s * s;
        dif += stack[p - 1].val;
        current -= stack[p - 1].val;
        t = stack[p - 1].t;
        p--;
      }
      if (dif > 0) {
        stack[p].t = t;
        stack[p].val = dif;
        current += dif;
        p++;
      }
      lastLCP = val;
    }
    sum += (length - 1 - index[length - 1]) - lastLCP;
    while (p > 0) {
      long long int s = (length - stack[p - 1].t);
      sum += stack[p - 1].val * s * s;
      p--;
    }
    delete[] lcp;
  }
  delete[] index;
  return sum;
}