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 state {
  long long len, link;
  long long size;
  long long firstpos;
  long long is_clone;
  long long son;
  vector<long long> v;
  long long next[26];
  long long size1;
};
const long long MAXLEN = 500010;
state st[MAXLEN];
long long sz, last;
void sam_init() {
  st[0].len = 0;
  st[0].link = -1;
  sz = 1;
  last = 0;
}
void sam_extend(char c) {
  long long cur = sz++;
  st[cur].len = st[last].len + 1;
  long long p = last;
  st[cur].size = 1;
  st[cur].firstpos = st[cur].len - 1;
  while (p != -1 && !st[p].next[c - 'a']) {
    st[p].next[c - 'a'] = cur;
    p = st[p].link;
  }
  if (p == -1) {
    st[cur].link = 0;
  } else {
    long long q = st[p].next[c - 'a'];
    if (st[p].len + 1 == st[q].len) {
      st[cur].link = q;
    } else {
      long long clone = sz++;
      st[clone].len = st[p].len + 1;
      memcpy(st[clone].next, st[q].next, sizeof(st[q].next));
      st[clone].link = st[q].link;
      while (p != -1 && st[p].next[c - 'a'] == q) {
        st[p].next[c - 'a'] = clone;
        p = st[p].link;
      }
      st[clone].firstpos = st[q].firstpos;
      st[clone].is_clone = 1;
      st[q].link = st[cur].link = clone;
    }
  }
  last = cur;
}
char s[MAXLEN];
long long t[MAXLEN];
long long A[MAXLEN];
void size_cal() {
  for (long long i = 1; i < sz; i++) t[st[i].len]++;
  for (long long i = 1; i < sz; i++) t[i] += t[i - 1];
  for (long long i = 1; i < sz; i++) A[t[st[i].len]--] = i;
  for (long long i = sz - 1; i >= 1; i--) {
    long long now = A[i];
    st[st[now].link].size += st[now].size;
  }
}
long long max1[MAXLEN];
long long min1[MAXLEN];
void match(char *s) {
  long long now = 0;
  long long l = 0;
  long long n = strlen(s);
  for (long long i = 0; i < n; i++) {
    if (st[now].next[s[i] - 'a']) {
      l++;
      now = st[now].next[s[i] - 'a'];
      max1[now] = max(max1[now], l);
    } else {
      while (now != -1 && !st[now].next[s[i] - 'a']) {
        now = st[now].link;
      }
      if (now == -1) {
        now = 0;
        l = 0;
      } else {
        l = st[now].len + 1;
        now = st[now].next[s[i] - 'a'];
        max1[now] = max(max1[now], l);
      }
    }
  }
  for (long long i = sz - 1; i >= 1; i--) {
    long long p = A[i];
    max1[st[p].link] = max(max1[st[p].link], max1[p]);
    max1[st[p].link] = min(max1[st[p].link], st[st[p].link].len);
  }
  for (long long i = 1; i < sz; i++) {
    min1[i] = min(min1[i], max1[i]);
    max1[i] = 0;
  }
}
char s1[10][MAXLEN];
signed main() {
  long long tt;
  cin >> tt;
  while (tt--) {
    sam_init();
    cin >> s;
    long long len = strlen(s);
    for (long long i = 0; i < len; i++) {
      sam_extend(s[i]);
    }
    size_cal();
    long long sum = 0;
    for (long long i = 1; i < sz; i++) {
      sum += (st[i].len - st[st[i].link].len) * st[i].size * st[i].size;
    }
    cout << sum << endl;
    for (long long i = 0; i < sz; i++) {
      st[i].len = st[i].link = st[i].size = 0;
      memset(st[i].next, 0, sizeof(st[i].next));
      t[i] = A[i] = 0;
    }
  }
}