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;
struct SuffixTree {
  const int INF = 1e9;
  vector<map<int, int> > to;
  vector<int> fpos;
  vector<int> link;
  vector<int> len;
  string s;
  int node;
  int pos;
  int sz;
  int n;
  SuffixTree(string s) : s(s), node(0), pos(0), sz(1), n(0) {
    int maxn = s.size() * 2 + 10;
    to.resize(maxn);
    len.resize(maxn);
    len[0] = INF;
    fpos.resize(maxn);
    link.resize(maxn);
    for (auto c : s) {
      addLetter(c);
    }
    for (int i = 1; i < sz; ++i) {
      len[i] = min(len[i], n - fpos[i]);
    }
  }
  int makeNode(int _pos, int _len) {
    fpos[sz] = _pos;
    len[sz] = _len;
    return sz++;
  }
  void goEdge() {
    while (pos > len[to[node][s[n - pos]]]) {
      node = to[node][s[n - pos]];
      pos -= len[node];
    }
  }
  void addLetter(int c) {
    n++;
    pos++;
    int last = 0;
    while (pos > 0) {
      goEdge();
      int edge = s[n - pos];
      int &v = to[node][edge];
      int t = s[fpos[v] + pos - 1];
      if (v == 0) {
        v = makeNode(n - pos, INF);
        link[last] = node;
        last = 0;
      } else if (t == c) {
        link[last] = node;
        return;
      } else {
        int u = makeNode(fpos[v], pos - 1);
        to[u][c] = makeNode(n - 1, INF);
        to[u][t] = v;
        fpos[v] += pos - 1;
        len[v] -= pos - 1;
        v = u;
        link[last] = u;
        last = u;
      }
      if (node == 0) {
        pos--;
      } else {
        node = link[node];
      }
    }
  }
  void printTree() {
    for (int i = 0; i < sz; ++i) {
      for (auto it : to[i]) {
        int v = it.second;
        cout << i << " " << v << " " << s.substr(fpos[v], len[v]) << endl;
      }
    }
  }
};
long long ans = 0;
int dfs(int u, SuffixTree *st) {
  bool isLeaf = true;
  int ret = 0;
  for (auto cv : st->to[u]) {
    ret += dfs(cv.second, st);
    isLeaf = false;
  }
  ret += isLeaf;
  if (u != 0) {
    int len = st->len[u] - isLeaf;
    long long cnt = ret;
    ans += cnt * cnt * len;
  }
  return ret;
}
int main() {
  std::ios::sync_with_stdio(false);
  cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    string s;
    cin >> s;
    ans = 0;
    SuffixTree suffixTree(s + '$');
    dfs(0, &suffixTree);
    cout << ans << endl;
  }
}