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 node {
  node *par, *suffixlink, *chd[27];
  int l, r, pardp, children, son;
  node() {
    par = suffixlink = NULL;
    for (int i = 0; i < 27; i++) chd[i] = NULL;
    l = r = pardp = children = son = 0;
  }
  inline int len() { return r - l; }
  inline int depth() { return pardp + len(); }
  inline bool inedge(int pos) { return pardp <= pos && pos < depth(); }
  void setedge(node *child, int l, int r, char *s) {
    chd[s[l]] = child;
    children++;
    child->par = this;
    child->pardp = depth();
    child->l = l, child->r = r;
  }
};
struct Suffix_Tree {
  char *s;
  int length, size;
  bool needwalk;
  node *root, *cur, *needsuffixlink;
  vector<node> v;
  node *newnode() {
    v[size] = node();
    return &v[size++];
  }
  void assign(char *str, int len) {
    s = str;
    length = len;
    size = 0;
    v.clear();
    v.reserve(length * 2 + 7);
    root = newnode();
    cur = newnode();
    root->setedge(cur, 0, length, s);
    needsuffixlink = NULL;
    needwalk = 1;
  }
  void walkdown(int i, int j) {
    if (i > j) return;
    for (int k = i + cur->depth(); !cur->inedge(j - i); k += cur->len())
      cur = cur->chd[s[k]];
  }
  void addsuffixlink() {
    if (needsuffixlink) needsuffixlink->suffixlink = cur;
    needsuffixlink = NULL;
  }
  void build(char *str, int len) {
    assign(str, len);
    for (int i = 0, j = 1; i < len; i++) {
      char c = s[i + 1];
      node *leaf, *split;
      for (; j <= i + 1; j++) {
        if (needwalk) {
          if (!cur->suffixlink && cur->par) cur = cur->par;
          cur = cur->suffixlink ? cur->suffixlink : root;
          walkdown(j, i);
        }
        needwalk = 1;
        int k = i - j + 1;
        if (k == cur->depth()) {
          addsuffixlink();
          if (cur->chd[c]) {
            cur = cur->chd[c], needwalk = 0;
            break;
          } else {
            leaf = newnode();
            cur->setedge(leaf, i + 1, length, s);
          }
        } else {
          int pos = cur->l + k - cur->pardp;
          if (s[pos] == c) {
            addsuffixlink();
            if (pos != i + 1) {
              needwalk = 0;
              break;
            }
          } else {
            split = newnode(), leaf = newnode();
            cur->par->setedge(split, cur->l, pos, s);
            cur->par->children--;
            split->setedge(cur, pos, cur->r, s);
            split->setedge(leaf, i + 1, length, s);
            cur = split;
            addsuffixlink();
            if (cur->depth() == 1)
              cur->suffixlink = root;
            else
              needsuffixlink = cur;
          }
        }
      }
    }
  }
  void pre(node *x) {
    x->son = 0;
    if (!x->children) {
      x->son = 1;
      return;
    }
    for (int i = 0; i < 27; i++)
      if (x->chd[i]) {
        node *y = x->chd[i];
        pre(y);
        if (y->len() == 0) x->son = 1;
      }
  }
  long long dfs(node *x) {
    long long rlt = 0;
    if (!x->children) return rlt;
    for (int i = 0; i < 27; i++)
      if (x->chd[i]) {
        node *y = x->chd[i];
        if (y->len() == 0) continue;
        rlt += dfs(y);
        x->son += y->son;
        int re = y->son;
        rlt += 1ll * (y->len()) * re * re;
      }
    return rlt;
  }
} ST;
int t;
char s[100100];
int main() {
  scanf("%d", &t);
  while (t--) {
    scanf("%s", s);
    int n = strlen(s);
    for (int i = 0; i < n; i++) s[i] -= 'a' - 1;
    ST.build(s, n);
    ST.pre(ST.root);
    printf("%I64d\n", ST.dfs(ST.root));
  }
  return 0;
}