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;
char s[200010];
class Automata {
 public:
  struct data {
    int link, len, cnt, dist;
    int next[27];
    data() {}
    data(int link, int len) : link(link), len(len) {}
  };
  data *node;
  int mat[200010], hit_node[200010];
  int num, last;
  set<pair<int, int> > st;
  void reset() {
    num = 1;
    node[0].link = -1;
    node[0].len = 0;
    node[0].cnt = 0;
    last = 0;
    memset(node[0].next, 0, sizeof(node[0].next));
  }
  Automata() {}
  Automata(int mx_len) {
    mx_len += 7;
    mx_len = mx_len * 2;
    node = new data[mx_len];
    memset(mat, 0x3f, sizeof(mat));
    reset();
  }
  void addLetter(char ch) {
    int cur = num++;
    int let = ch - 'a';
    int p = last;
    node[cur].len = node[last].len + 1;
    node[cur].cnt = 1;
    st.insert({node[cur].len, cur});
    memset(node[cur].next, 0, sizeof(node[cur].next));
    for (p = last; p != -1 && !node[p].next[let]; p = node[p].link)
      node[p].next[let] = cur;
    if (p == -1)
      node[cur].link = 0;
    else {
      int q = node[p].next[let];
      if (node[p].len + 1 == node[q].len)
        node[cur].link = q;
      else {
        int clone = num++;
        node[clone] = node[q];
        node[clone].len = node[p].len + 1;
        node[clone].cnt = 0;
        st.insert({node[clone].len, clone});
        for (; p != -1 && node[p].next[let] == q; p = node[p].link)
          node[p].next[let] = clone;
        node[q].link = node[cur].link = clone;
      }
    }
    last = cur;
  }
  void count_sub_str() {
    for (auto it = st.rbegin(); it != st.rend(); it++) {
      node[node[it->second].link].cnt += node[it->second].cnt;
    }
  }
  void count_dist_str(int x) {
    if (node[x].dist) return;
    node[x].dist = 1;
    for (int i = 0; i < 26; i++)
      if (node[x].next[i]) {
        count_dist_str(node[x].next[i]);
        node[x].dist += node[node[x].next[i]].dist;
      }
  }
};
Automata sa;
int main() {
  int tc;
  scanf("%d", &tc);
  while (tc--) {
    scanf("%s", s);
    int sz = strlen(s);
    sa = Automata(sz);
    for (int i = 0; i < sz; i++) sa.addLetter(s[i]);
    long long ans = 0;
    sa.count_sub_str();
    for (int i = 1; i < sa.num; i++)
      ans += 1LL * sa.node[i].cnt * sa.node[i].cnt *
             (sa.node[i].len - sa.node[sa.node[i].link].len);
    printf("%lld\n", ans);
  }
}