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;
int t, n;
long long res;
string s;
vector<int> sa;
pair<int, int> cmp[100007];
int pos[100007];
int nast[100007];
int lcp[100007];
int size[100007];
int load[2 * (1 << 17)];
void clear() {
  memset(lcp, 0, sizeof lcp);
  memset(size, 0, sizeof size);
  memset(nast, 0, sizeof nast);
  memset(pos, 0, sizeof pos);
  sa.clear();
  res = 0;
}
bool comp(int a, int b) { return cmp[a] < cmp[b]; }
void build() {
  memset(load, 0, sizeof load);
  for (int i = 1; i <= n; ++i) {
    load[i + (1 << 17)] = i;
  }
  for (int i = (1 << 17) - 1; i >= 1; --i) {
    if (lcp[load[2 * i]] < lcp[load[2 * i + 1]])
      load[i] = load[2 * i];
    else
      load[i] = load[2 * i + 1];
  }
}
void update(int a) {
  a += (1 << 17);
  load[a] = 0;
  a /= 2;
  while (a >= 1) {
    if (lcp[load[2 * a]] < lcp[load[2 * a + 1]])
      load[a] = load[2 * a];
    else
      load[a] = load[2 * a + 1];
    a /= 2;
  }
}
int query(int a, int b) {
  a += (1 << 17);
  b += (1 << 17);
  int res = 0;
  if (lcp[load[a]] < lcp[res]) res = load[a];
  if (lcp[load[b]] < lcp[res]) res = load[b];
  while (a < b - 1) {
    if (a % 2 == 0 && lcp[load[a + 1]] < lcp[res]) res = load[a + 1];
    if (b % 2 == 1 && lcp[load[b - 1]] < lcp[res]) res = load[b - 1];
    a /= 2;
    b /= 2;
  }
  return res;
}
void solve(int a, int b, int last) {
  vector<int> v;
  int q = query(a, b), val = lcp[q];
  if (val == 1000000007) {
    res += (long long)(size[a] - last - 1);
    return;
  } else {
    while (lcp[q] == val) {
      v.push_back(q);
      update(q);
      q = query(a, b);
    }
  }
  res += (long long)(b - a + 1) * (b - a + 1) * (val - last - 1);
  sort((v).begin(), (v).end());
  res += (long long)(v[0] - a + 1) * (v[0] - a + 1);
  solve(a, v[0], lcp[v[0]]);
  res += (long long)(b - v.back()) * (b - v.back());
  solve(v.back() + 1, b, lcp[v[0]]);
  for (int i = 0; i + 1 < v.size(); ++i) {
    res += (long long)(v[i + 1] - v[i]) * (v[i + 1] - v[i]);
    solve(v[i] + 1, v[i + 1], lcp[v[0]]);
  }
}
void test() {
  cin >> s;
  n = s.size();
  s = '#' + s;
  for (int i = 1; i <= n; ++i) {
    sa.push_back(i);
    cmp[i] = make_pair(s[i], -1);
  }
  sort((sa).begin(), (sa).end(), comp);
  for (int i = 0; i < n; ++i) {
    if (i > 0 && cmp[sa[i - 1]] == cmp[sa[i]])
      pos[sa[i]] = pos[sa[i - 1]];
    else
      pos[sa[i]] = i;
  }
  for (int l = 0; (1 << l) < n; ++l) {
    for (int i = 1; i <= n; ++i) {
      if (i + (1 << l) <= n)
        cmp[i] = make_pair(pos[i], pos[i + (1 << l)]);
      else
        cmp[i] = make_pair(pos[i], -1);
    }
    sort((sa).begin(), (sa).end(), comp);
    for (int i = 0; i < n; ++i) {
      if (i > 0 && cmp[sa[i - 1]] == cmp[sa[i]])
        pos[sa[i]] = pos[sa[i - 1]];
      else
        pos[sa[i]] = i;
    }
  }
  for (int i = 0; i < n - 1; ++i) {
    nast[sa[i]] = sa[i + 1];
  }
  for (int i = 0; i < n; ++i) {
    pos[sa[i]] = i;
    size[i + 1] = n - sa[i] + 1;
  }
  int curr = 0;
  for (int i = 1; i <= n; ++i) {
    if (!nast[i]) continue;
    while (curr + 1 <= min(n - i + 1, n - nast[i] + 1) &&
           s[i + curr] == s[nast[i] + curr])
      ++curr;
    lcp[pos[i] + 1] = curr;
    curr = max(0, curr - 1);
  }
  lcp[n] = lcp[0] = 1000000007;
  build();
  solve(1, n, -1);
  cout << res << '\n';
  clear();
}
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);
  cin >> t;
  while (t--) test();
}