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 = 100005, M = 100005, mod = 1e9 + 7;
template <class T>
inline void gmin(T &x, const T &y) {
  if (x > y) x = y;
}
template <class T>
inline void gmax(T &x, const T &y) {
  if (x < y) x = y;
}
inline void ch(int &x, int y) { x = (x + y) % mod; }
template <class T>
inline void read(T &x) {
  x = 0;
  char ch = getchar();
  while (ch > '9' || ch < '0') ch = getchar();
  while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
}
template <class T>
inline void print(T x) {
  if (!x) {
    puts("0");
    return;
  }
  int a[20], m = 0;
  while (x) a[m++] = x % 10, x /= 10;
  while (m--) putchar(a[m] + '0');
  puts("");
}
struct node {
  int x, num;
} p[N];
inline bool cmp(const node &a, const node &b) { return a.x < b.x; }
set<int> a;
char s[N];
int n, lcp[N];
namespace sufarr {
int sa[N], rank[N], c[N], tmp[N];
void getsa() {
  int m = 300;
  memset(c, 0, sizeof(c));
  for (int i = 1; i <= n; i++) rank[i] = s[i];
  for (int i = 1; i <= n; i++) c[rank[i]]++;
  for (int i = 1; i <= m; i++) c[i] += c[i - 1];
  for (int i = 1; i <= n; i++) sa[c[rank[i]]] = i, c[rank[i]]--;
  for (int k = 1; k < n; k <<= 1) {
    int tot = 0;
    for (int i = n - k + 1; i <= n; i++) tmp[++tot] = i;
    for (int i = 1; i <= n; i++)
      if (sa[i] > k) tmp[++tot] = sa[i] - k;
    for (int i = 1; i <= m; i++) c[i] = 0;
    for (int i = 1; i <= n; i++) c[rank[i]]++;
    for (int i = 1; i <= m; i++) c[i] += c[i - 1];
    for (int i = n; i; i--) sa[c[rank[tmp[i]]]] = tmp[i], c[rank[tmp[i]]]--;
    tmp[sa[1]] = 1;
    for (int i = 2; i <= n; i++) {
      int p = sa[i - 1], q = sa[i];
      tmp[q] = tmp[p];
      if (rank[p] != rank[q] || rank[p + k] != rank[q + k]) tmp[q]++;
    }
    memcpy(rank, tmp, sizeof(rank));
    m = rank[sa[n]];
    if (m == n) break;
  }
}
void getlcp() {
  for (int i = 1; i <= n; i++) tmp[sa[i]] = i;
  int k = 0;
  for (int i = 1; i <= n; i++) {
    if (k) k--;
    while (s[i + k] == s[sa[tmp[i] + 1] + k]) k++;
    lcp[tmp[i]] = k;
  }
}
}  // namespace sufarr
bool solve() {
  scanf("%s", s + 1);
  n = strlen(s + 1);
  sufarr::getsa();
  sufarr::getlcp();
  a.clear();
  a.insert(0);
  a.insert(n);
  for (int i = 1; i < n; i++) p[i] = (node){lcp[i], i};
  sort(p + 1, p + n, cmp);
  long long ans = (long long)n * (n + 1) / 2;
  for (int i = 1; i < n; i++) {
    set<int>::iterator it = a.lower_bound(p[i].num);
    int r = *it, l = *(--it);
    ans += (long long)(p[i].num - l) * (r - p[i].num) * p[i].x * 2;
    a.insert(p[i].num);
  }
  printf("%lld\n", ans);
  return 0;
}
int main() {
  ios::sync_with_stdio(0);
  int T;
  read(T);
  while (T--) solve();
  return 0;
}