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 MN = 1e5 + 10, B = 727;
int h[MN], Id[MN], arr[MN], pw[MN], n;
string s;
pair<int, int> T[MN];
int get(int l, int r) { return h[r] - h[l] * pw[r - l]; }
int G(int x, int y) {
  int L = 0, R = n - max(x, y);
  while (L ^ R) {
    int mid = L + R + 1 >> 1;
    if (get(x, x + mid) == get(y, y + mid))
      L = mid;
    else
      R = mid - 1;
  }
  return L;
}
bool cmp(int x, int y) {
  int p = G(x, y);
  return s[p + x] < s[y + p];
}
int main() {
  ios_base ::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  int Tst;
  cin >> Tst;
  pw[0] = 1;
  for (int i = 1; i < MN; ++i) pw[i] = B * pw[i - 1];
  while (Tst--) {
    cin >> s;
    n = ((int)(s).size());
    s += char('a' - 1);
    for (int i = 0; i < n; ++i) h[i + 1] = h[i] * B + (s[i] - 'a' + 1);
    iota(Id, Id + n, 0);
    sort(Id, Id + n, cmp);
    for (int i = 0; i < n - 1; ++i)
      arr[i] = G(Id[i], Id[i + 1]), T[i] = {arr[i], i};
    set<int> S = {-1, n - 1};
    set<int>::iterator it;
    sort(T, T + n - 1);
    long long ans = 0;
    for (int i = 0; i < n - 1; ++i) {
      int id = T[i].second;
      it = S.upper_bound(id);
      int x = *it - id;
      --it;
      int y = id - *it;
      S.insert(id);
      ans += 1ll * x * y * T[i].first;
    }
    cout << ans * 2 + 1ll * n * (n + 1) / 2 << '\n';
  }
  return 0;
}