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 double eps = 1e-8;
const int inf = 0x3f3f3f3f;
const int Minf = 0x7f7f7f7f;
const long long INF = 0x3f3f3f3f3f3f3f3fll;
const long long MINF = 0x7f7f7f7f7f7f7f7fll;
const int N = 1e5 + 50;
struct node {
  int son[26];
  int len;
  int link;
};
struct Tree {
  int head[N * 2], to[N * 2], nxt[N * 2], tot;
  int siz[N * 2];
  void clr() {
    memset(head, 0, sizeof head);
    memset(to, 0, sizeof to);
    memset(siz, 0, sizeof siz);
    memset(nxt, 0, sizeof nxt);
    tot = 0;
  }
  void add(int x, int y) {
    to[++tot] = y;
    nxt[tot] = head[x];
    head[x] = tot;
  }
  void get_siz(int now) {
    for (int i = head[now]; i; i = nxt[i]) {
      get_siz(to[i]);
      siz[now] += siz[to[i]];
    }
  }
};
struct SAM {
  node t[N * 2];
  int siz, lst;
  Tree T;
  void init() {
    t[1].len = 0;
    t[1].link = 0;
    siz = 1;
    lst = 1;
  }
  void clr() {
    T.clr();
    for (int i = (1); i <= (siz); ++i) {
      t[i].len = 0;
      t[i].link = 0;
      for (int j = (0); j < (26); ++j) t[i].son[j] = 0;
    }
    init();
  }
  void insert(int c) {
    int np = ++siz, p = lst;
    t[np].len = t[p].len + 1;
    while (p != 0 && t[p].son[c] == 0) t[p].son[c] = np, p = t[p].link;
    if (p == 0)
      t[np].link = 1;
    else {
      int q = t[p].son[c];
      if (t[p].len + 1 == t[q].len) {
        t[np].link = q;
      } else {
        int nq = ++siz;
        t[nq].len = t[p].len + 1;
        t[nq].link = t[q].link;
        for (int i = (0); i < (26); ++i) t[nq].son[i] = t[q].son[i];
        while (p != 0 && t[p].son[c] == q) {
          t[p].son[c] = nq;
          p = t[p].link;
        }
        t[q].link = t[np].link = nq;
      }
    }
    lst = np;
    T.siz[np] = 1;
  }
  long long getans() {
    for (int i = (2); i <= (siz); ++i) {
      T.add(t[i].link, i);
    }
    T.get_siz(1);
    long long ans = 0;
    for (int i = (2); i <= (siz); ++i) {
      ans += 1ll * (t[i].len - t[t[i].link].len) * T.siz[i] * T.siz[i];
    }
    return ans;
  }
} s;
char S[N];
int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    scanf("%s", S + 1);
    int n = strlen(S + 1);
    s.clr();
    for (int i = (1); i <= (n); ++i) s.insert(S[i] - 'a');
    cout << s.getans() << endl;
  }
  return 0;
}