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 V = 1000010;
char get() {
  static char buf[V], *p1 = buf, *p2 = buf;
  if (p1 == p2) {
    p2 = (p1 = buf) + fread(buf, 1, V, stdin);
    if (p1 == p2) return EOF;
  }
  return *p1++;
}
void Read(int &x) {
  x = 0;
  static char c;
  for (; !isdigit(c); c = get())
    ;
  for (; isdigit(c); x = x * 10 + c - '0', c = get())
    ;
}
void Read(char *s, int &len) {
  len = 0;
  static char c;
  for (; !islower(c); c = get())
    ;
  for (; islower(c); s[len++] = c, c = get())
    ;
}
long long Ans;
namespace SAM {
int fa[V << 1], len[V << 1], val[V << 1], c[V << 1][26];
int rt, lst, pT;
void init() {
  for (int i = 1; i <= pT; i++) {
    fa[i] = len[i] = val[i] = 0;
    for (int j = 0; j < 26; j++) c[i][j] = 0;
  }
  rt = lst = pT = 1;
}
void extend(int x) {
  int cur = ++pT;
  len[cur] = len[lst] + 1;
  val[cur] = 1;
  int p = lst;
  while (p && !c[p][x]) c[p][x] = cur, p = fa[p];
  if (!p)
    fa[cur] = rt;
  else {
    int q = c[p][x];
    if (len[q] == len[p] + 1)
      fa[cur] = q;
    else {
      ++pT;
      len[pT] = len[p] + 1;
      fa[pT] = fa[q];
      memcpy(c[pT], c[q], sizeof c[q]);
      while (c[p][x] == q) c[p][x] = pT, p = fa[p];
      fa[q] = fa[cur] = pT;
    }
  }
  lst = cur;
}
int q[V << 1], id[V << 1];
void work(int n) {
  for (int i = 1; i <= n; i++) q[i] = 0;
  for (int i = 1; i <= pT; i++) q[len[i]]++;
  for (int i = 1; i <= pT; i++) q[i] += q[i - 1];
  for (int i = pT; i; i--) id[q[len[i]]--] = i;
  for (int i = pT; i; i--) {
    int t = id[i];
    Ans += (long long)val[t] * val[t] * (len[t] - len[fa[t]]);
    val[fa[t]] += val[t];
  }
}
}  // namespace SAM
int T, n;
char s[V];
int main() {
  Read(T);
  while (T--) {
    Ans = 0;
    Read(s + 1, n);
    SAM::init();
    for (int i = 1; i <= n; i++) SAM::extend(s[i] - 'a');
    SAM::work(n);
    cout << Ans << endl;
  }
  return 0;
}