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 long long MAXN = 2e5 + 7;
const long long K = 26;
struct Node {
  bool term;
  long long link, len;
  map<char, long long> go;
};
Node d[MAXN];
bool used[MAXN];
long long dp1[MAXN], dp2[MAXN];
long long last = -1;
long long u = -1;
void add(char c) {
  long long curr = u++;
  d[curr].len = d[last].len + 1;
  long long p;
  for (p = last; p != -1 && d[p].go.find(c) == d[p].go.end(); p = d[p].link) {
    d[p].go[c] = curr;
  }
  if (p == -1) {
    d[curr].link = 0;
  } else {
    long long q = d[p].go[c];
    if (d[p].len + 1 == d[q].len) {
      d[curr].link = q;
    } else {
      long long clone = u++;
      d[clone].link = d[q].link;
      d[clone].len = d[p].len + 1;
      d[clone].go = d[q].go;
      d[q].link = d[curr].link = clone;
      for (long long t = p; t != -1 && d[t].go[c] == q; t = d[t].link) {
        d[t].go[c] = clone;
      }
    }
  }
  last = curr;
}
vector<long long> topsort;
void dfs(long long u) {
  used[u] = 1;
  for (auto e : d[u].go) {
    long long v = e.second;
    if (!used[v]) {
      dfs(v);
    }
  }
  topsort.push_back(u);
}
void solve() {
  for (long long i = 0; i < MAXN; ++i) {
    dp1[i] = dp2[i] = 0;
    d[i].term = 0;
    d[i].link = -1;
    d[i].len = 0;
    d[i].go.clear();
  }
  string s;
  cin >> s;
  last = 0;
  u = 1;
  for (char c : s) {
    add(c);
  }
  topsort.clear();
  memset(used, 0, sizeof used);
  dfs(0);
  reverse(topsort.begin(), topsort.end());
  dp1[0] = 1;
  for (long long u : topsort) {
    for (auto e : d[u].go) {
      long long v = e.second;
      dp1[v] += dp1[u];
    }
  }
  long long t = last;
  while (t != -1) {
    d[t].term = 1;
    t = d[t].link;
  }
  reverse(topsort.begin(), topsort.end());
  for (long long u : topsort) {
    dp2[u] = d[u].term;
    for (auto e : d[u].go) {
      long long v = e.second;
      dp2[u] += dp2[v];
    }
  }
  long long ans = 0;
  for (long long i = 1; i < u; ++i) {
    ans += dp1[i] * dp2[i] * dp2[i];
  }
  cout << ans << '\n';
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  long long t;
  cin >> t;
  for (long long i = 0; i < t; ++i) {
    solve();
  }
  return 0;
}