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>
template <class _Type>
void logArray(_Type a[], int n) {
  for (int i = 0; i < n; ++i) std::cout << a[i] << ' ';
  std::cout << std::endl;
}
template <class T>
inline bool checkMin(T& a, T b) {
  return (a > b ? a = b, 1 : 0);
}
template <class T>
inline bool checkMax(T& a, T b) {
  return (a < b ? a = b, 1 : 0);
}
void preInit();
void init();
void solve();
int32_t main() {
  preInit();
  int T;
  scanf("%d", &T);
  while (T--) {
    init();
    solve();
  }
  return 0;
}
const int N = 100005;
const int C = 26;
struct SAM {
  struct Node {
    std::size_t len = 0, size = 1, ref = 0;
    int link = -1, next[C];
    Node() { memset(next, -1, sizeof(next)); }
  };
  Node p[N * 2];
  static constexpr int root = 0;
  int last = root;
  int cnt = root + 1;
  void clear() {
    while (cnt) {
      p[--cnt] = Node();
    }
    cnt = 1;
    last = 0;
  }
  void insert(std::size_t c) {
    int cur = cnt++;
    p[cur].len = p[last].len + 1;
    int pos = last;
    while (pos != -1) {
      if (p[pos].next[c] != -1) {
        break;
      }
      p[pos].next[c] = cur;
      pos = p[pos].link;
    }
    if (pos == -1) {
      p[cur].link = 0;
    } else {
      int q = p[pos].next[c];
      if (p[q].len == p[pos].len + 1) {
        p[cur].link = q;
      } else {
        int clone = cnt++;
        p[clone] = p[q];
        p[clone].len = p[pos].len + 1;
        p[clone].size = 0;
        p[q].link = p[cur].link = clone;
        while (pos != -1 && p[pos].next[c] == q) {
          p[pos].next[c] = clone;
          pos = p[pos].link;
        }
      }
    }
    last = cur;
  }
  void buildSize() {
    for (int i = 1; i < cnt; ++i) {
      p[p[i].link].ref++;
    }
    std::queue<int> que;
    for (int i = 0; i < cnt; ++i)
      if (p[i].ref == 0) {
        que.push(i);
      }
    while (!que.empty()) {
      int u = que.front();
      que.pop();
      int fa = p[u].link;
      if (fa != -1) {
        p[fa].size += p[u].size;
        p[fa].ref--;
        if (p[fa].ref == 0) {
          que.push(fa);
        }
      }
    }
  }
  unsigned long long solve() {
    buildSize();
    unsigned long long res = 0;
    for (int i = 1; i < cnt; ++i) {
      res += static_cast<unsigned long long>(p[i].len - p[p[i].link].len) *
             p[i].size * p[i].size;
    }
    return res;
  }
} sam;
int n;
char s[N];
void preInit() {}
void init() { sam.clear(); }
void solve() {
  scanf("%s", s);
  n = std::strlen(s);
  for (int i = 0; i < n; i++) {
    sam.insert(s[i] - 'a');
  }
  printf("%llu\n", sam.solve());
}