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 int N = 200000 + 5;
struct Node {
  int ch[26], fa, len;
} nd[N];
struct Edge {
  int next, to;
} edge[N];
char op[N];
int l, ct = 1, last = 1, f[N], head[N], cnt;
inline int newNode() {
  ++ct;
  for (int i = 0; i < 26; i++) nd[ct].ch[i] = 0;
  head[ct] = 0, nd[ct].fa = nd[ct].len = f[ct] = 0;
  return ct;
}
inline void add(int x, int y) {
  edge[cnt].to = y, edge[cnt].next = head[x], head[x] = cnt++;
}
inline void add(int c) {
  int p = last, np = last = newNode();
  nd[np].len = nd[p].len + 1, f[np] = 1;
  while (p && !nd[p].ch[c]) nd[p].ch[c] = np, p = nd[p].fa;
  if (!p)
    nd[np].fa = 1;
  else {
    int q = nd[p].ch[c];
    if (nd[q].len == nd[p].len + 1)
      nd[np].fa = q;
    else {
      int nq = newNode();
      nd[nq] = nd[q], nd[nq].len = nd[p].len + 1, nd[q].fa = nd[np].fa = nq;
      while (p && nd[p].ch[c] == q) nd[p].ch[c] = nq, p = nd[p].fa;
    }
  }
}
void DFS(int x) {
  if (x == 0) return;
  for (int i = head[x]; i; i = edge[i].next)
    DFS(edge[i].to), f[x] += f[edge[i].to];
}
long long ans = 0;
int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    scanf("%s", op), l = strlen(op);
    cnt = ct = last = 1, head[1] = ans = 0;
    for (int i = 0; i < 26; i++) nd[1].ch[i] = 0;
    f[1] = nd[1].fa = nd[1].len = 0;
    for (int i = 0; i < l; i++) add(op[i] - 'a');
    for (int i = 2; i <= ct; i++) add(nd[i].fa, i);
    DFS(1);
    for (int i = 2; i <= ct; i++) {
      ans += 1ll * (nd[i].len - nd[nd[i].fa].len) * f[i] * f[i];
    }
    printf("%lld\n", ans);
  }
  return 0;
}