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;
using ll = long long;
using pii = pair<int, int>;
mt19937 gen(chrono::steady_clock::now().time_since_epoch().count());
template <typename... T>
void rd(T&... args) {
  ((cin >> args), ...);
}
template <typename... T>
void wr(T... args) {
  ((cout << args << " "), ...);
  cout << endl;
}
struct SAM {
  vector<unordered_map<char, int>> edges;
  vector<int> link;
  vector<int> length;
  vector<int> sz;
  int last;
  SAM(string s) {
    edges.emplace_back();
    link.push_back(-1);
    length.push_back(0);
    sz.push_back(0);
    last = 0;
    for (auto ch : s) {
      edges.emplace_back();
      length.push_back(length[last] + 1);
      link.push_back(0);
      sz.push_back(0);
      int r = edges.size() - 1;
      int p = last;
      while (p >= 0 && edges[p].find(ch) == edges[p].end()) {
        edges[p][ch] = r;
        p = link[p];
      }
      if (p != -1) {
        int q = edges[p][ch];
        if (length[p] + 1 == length[q]) {
          link[r] = q;
        } else {
          edges.push_back(edges[q]);
          length.push_back(length[p] + 1);
          link.push_back(link[q]);
          sz.push_back(0);
          int qq = edges.size() - 1;
          link[q] = qq;
          link[r] = qq;
          while (p >= 0 && edges[p][ch] == q) {
            edges[p][ch] = qq;
            p = link[p];
          }
        }
      }
      last = r;
      sz[last] = 1;
    }
  }
  void solve() {
    ll ans = 0;
    int cnt = link.size();
    vector<int> c(cnt), a(cnt);
    for (int i = 1; i < cnt; i++) c[length[i]]++;
    for (int i = 1; i < cnt; i++) c[i] += c[i - 1];
    for (int i = 1; i < cnt; i++) a[c[length[i]]--] = i;
    for (int i = cnt - 1; i > 0; i--) {
      int p = a[i];
      sz[link[p]] += sz[p];
      ans += ll(sz[p]) * sz[p] * (length[p] - length[link[p]]);
    }
    cout << ans << endl;
  }
};
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int tt;
  cin >> tt;
  while (tt--) {
    string s;
    cin >> s;
    SAM sam(s);
    sam.solve();
  }
  return 0;
}