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 MAX = 1e5 + 5;
int N;
char T[MAX];
int sa[MAX], tsa[MAX], ra[MAX], tra[MAX];
int lcp[MAX], plcp[MAX], phi[MAX], c[MAX];
void sort(int k) {
  memset(c, 0, sizeof c);
  for (int i = int(0); i < int(N); i++) {
    c[i + k < N ? ra[i + k] : 0]++;
  }
  int sum = 0, maxi = max(300, N);
  for (int i = int(0); i < int(maxi); i++) {
    int t = c[i];
    c[i] = sum;
    sum += t;
  }
  for (int i = int(0); i < int(N); i++) {
    int cur = sa[i] + k < N ? ra[sa[i] + k] : 0;
    tsa[c[cur]++] = sa[i];
  }
  memcpy(sa, tsa, sizeof(int) * N);
}
void build_sa() {
  for (int i = int(0); i < int(N); i++) {
    ra[i] = T[i];
    sa[i] = i;
  }
  for (int k = 1; k < N; k *= 2) {
    sort(k);
    sort(0);
    int r = tra[sa[0]] = 0;
    for (int i = int(1); i < int(N); i++) {
      if (ra[sa[i]] == ra[sa[i - 1]]) {
        int cur = (sa[i] + k) < N ? ra[sa[i] + k] : 0;
        int prev = (sa[i - 1] + k) < N ? ra[sa[i - 1] + k] : 0;
        if (cur == prev) {
          tra[sa[i]] = r;
        } else {
          tra[sa[i]] = ++r;
        }
      } else {
        tra[sa[i]] = ++r;
      }
    }
    if (tra[sa[N - 1]] == N - 1) {
      break;
    }
    memcpy(ra, tra, sizeof(int) * N);
  }
}
void build_lcp() {
  phi[sa[0]] = -1;
  for (int i = int(1); i < int(N); i++) {
    phi[sa[i]] = sa[i - 1];
  }
  int l = 0;
  for (int i = int(0); i < int(N); i++) {
    if (phi[i] == -1) {
      plcp[i] = 0;
      continue;
    }
    while (T[i + l] == T[phi[i] + l]) {
      l++;
    }
    plcp[i] = l;
    l = max(l - 1, 0);
  }
  for (int i = int(0); i < int(N); i++) {
    lcp[i] = plcp[sa[i]];
  }
}
long long naive(string s) {
  map<string, int> app;
  s.pop_back();
  for (int i = int(0); i < int(s.size()); i++) {
    for (int j = int(i); j < int(s.size()); j++) {
      app[s.substr(i, j - i + 1)]++;
    }
  }
  long long ans = 0;
  for (auto &each : app) {
    ans += 1LL * each.second * each.second;
  }
  return ans;
}
vector<int> guys[MAX];
int main() {
  int t;
  scanf("%d", &t);
  while (t--) {
    memset(T, 0, sizeof T);
    memset(lcp, 0, sizeof lcp);
    scanf("%s", T);
    N = strlen(T);
    T[N++] = '$';
    for (int i = int(0); i < int(N + 1); i++) {
      guys[i].clear();
    }
    build_sa();
    build_lcp();
    for (int i = int(1); i < int(N); i++) {
      guys[lcp[i]].push_back(i);
    }
    long long ans = (1LL * N * (N - 1)) / 2LL;
    set<int> s{0, N};
    for (int i = int(0); i < int(N + 1); i++) {
      if (i > 0) {
        set<pair<int, int> > u;
        for (auto &each : guys[i]) {
          auto it = s.lower_bound(each);
          auto pit = prev(it);
          u.emplace(*pit, *it);
        }
        for (auto &each : u) {
          int d = each.second - each.first;
          int maxx = max(lcp[each.second], lcp[each.first]);
          ans -= d * (i - maxx);
          ans += 1LL * d * d * (i - maxx);
        }
      }
      for (auto &each : guys[i]) {
        s.insert(each);
      }
    }
    printf("%lld\n", ans);
  }
  return 0;
}