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;
char buf[100010];
string s;
int N;
int sa[100010 + 10], sainv[100010 + 10], lcp[100010 + 10];
pair<pair<int, int>, int> p[100010 + 10], q[100010 + 10];
void suffix_array(void) {
  int i, j, tmp = 0;
  for ((i) = 0; (i) < (int)(N); (i)++) sainv[i] = s[i];
  for (int t = 1; t < N; t *= 2) {
    for ((i) = 0; (i) < (int)(N); (i)++)
      p[i] =
          make_pair(make_pair(sainv[i], ((i + t >= N) ? -1 : sainv[i + t])), i);
    sort(p, p + N);
    int sz = 0;
    for ((i) = 0; (i) < (int)(N); (i)++) {
      if (i > 0 && p[i].first != p[i - 1].first) sz++;
      sainv[p[i].second] = sz;
    }
  }
  for ((i) = 0; (i) < (int)(N); (i)++) sa[sainv[i]] = i;
  for ((i) = 0; (i) < (int)(N); (i)++)
    if (sainv[i] != N - 1) {
      j = sa[sainv[i] + 1];
      while (i + tmp < N && j + tmp < N && s[i + tmp] == s[j + tmp]) tmp++;
      lcp[sainv[i]] = tmp;
      if (tmp > 0) tmp--;
    }
}
long long main2(void) {
  int i, j, k;
  long long ans = 0;
  set<int> sep;
  sep.insert(0);
  sep.insert(N);
  vector<pair<int, int> > v;
  for ((i) = 0; (i) < (int)(N - 1); (i)++)
    v.push_back(make_pair(lcp[i], i + 1));
  sort(v.begin(), v.end());
  for ((i) = 0; (i) < (int)(v.size()); (i)++) {
    int x = v[i].second;
    long long val = v[i].first;
    sep.insert(x);
    __typeof(sep.begin()) itr = sep.find(x);
    itr--;
    int L = *(itr);
    itr++;
    itr++;
    int R = *(itr);
    ans += val * (x - L) * (R - x);
  }
  ans = 2 * ans;
  for (i = 1; i <= N; i++) ans += i;
  return ans;
}
int main(void) {
  int T, t;
  cin >> T;
  for ((t) = 0; (t) < (int)(T); (t)++) {
    scanf("%s", buf);
    s = buf;
    N = s.length();
    suffix_array();
    long long ans = main2();
    cout << ans << endl;
  }
  return 0;
}