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;
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) {
  cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
  const char* comma = strchr(names + 1, ',');
  cerr.write(names, comma - names) << " : " << arg1 << " | ";
  __f(comma + 1, args...);
}
namespace SuffixTree {
const int INF = 1e9, N = 1e6 + 10, dollar = 257;
int s[N];
map<int, int> to[N];
int len[N] = {INF}, fpos[N], link[N], suff[N], par[N];
int node, pos, remain;
int sz = 1, n = 0;
void init() {
  for (int i = (0); i < (max(sz, n)); ++i) {
    len[i] = fpos[i] = link[i] = suff[i] = par[i] = s[i] = 0;
    to[i].clear();
  }
  node = pos = remain = 0;
  sz = 1;
  n = 0;
  len[0] = INF;
}
int make_node(int _pos, int _len, int _par) {
  fpos[sz] = _pos;
  len[sz] = _len;
  suff[sz] = n - remain;
  par[sz] = _par;
  return sz++;
}
void go_edge() {
  while (pos > len[to[node][s[n - pos]]]) {
    node = to[node][s[n - pos]];
    pos -= len[node];
  }
}
void add_letter(int c) {
  s[n++] = c;
  int last = 0;
  for (remain++, pos++; pos > 0; remain--) {
    go_edge();
    int edge = s[n - pos];
    int& v = to[node][edge];
    int t = s[fpos[v] + pos - 1];
    if (v == 0) {
      v = make_node(n - pos, INF, node);
      link[last] = node;
      last = 0;
    } else if (t == c) {
      link[last] = node;
      return;
    } else {
      int u = make_node(fpos[v], pos - 1, node);
      to[u][c] = make_node(n - 1, INF, u);
      to[u][t] = v;
      par[v] = u;
      fpos[v] += pos - 1;
      len[v] -= pos - 1;
      v = u;
      link[last] = u;
      last = u;
    }
    if (node == 0)
      pos--;
    else
      node = link[node];
  }
}
}  // namespace SuffixTree
const int N = int(1e5) + 10;
char s[N];
int n;
long long int ans = 0;
long long int dfs(int x) {
  long long int ret = (SuffixTree::len[x] > n);
  for (auto it : SuffixTree::to[x]) {
    int y = it.second;
    int sub = dfs(y);
    int L = SuffixTree::fpos[y], R = min(n - 1, L + SuffixTree::len[y] - 1);
    int num = max(0, R - L + 1);
    ret += sub;
    ans += sub * 1ll * sub * 1ll * num;
  }
  return ret;
}
int main() {
  int t;
  scanf("%d", &t);
  while (t--) {
    scanf("%s", s);
    n = strlen(s);
    SuffixTree::init();
    for (int i = (0); i < (n); ++i) SuffixTree::add_letter(s[i]);
    SuffixTree::add_letter(SuffixTree::dollar);
    ans = 0;
    dfs(0);
    printf("%lld\n", ans);
  }
  return 0;
}