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>
#pragma warning(disable : 4996)
using namespace std;
void radixSort(vector<int> &A, vector<int> &B, vector<int> &C, int N, int M) {
  vector<int> D(M, 0);
  for (int i = 0; i < N; i++) D[B[A[i]]]++;
  for (int i = 1; i < M; i++) D[i] += D[i - 1];
  for (int i = N - 1; i >= 0; i--) C[--D[B[A[i]]]] = A[i];
}
vector<int> T, B;
void suffixArray(string &S, vector<int> &C, int N) {
  T.resize(N);
  B.resize(N);
  C.resize(N);
  for (int i = 0; i < N; i++) {
    B[i] = S[i];
    T[i] = i;
  }
  radixSort(T, B, C, N, 129);
  for (int i = 1; i < N; i <<= 1) {
    int k = 0;
    for (int j = 0; j < i; j++) T[k++] = N - i + j;
    for (int j = 0; j < N; j++)
      if (C[j] >= i) T[k++] = C[j] - i;
    radixSort(T, B, C, N, max(N, 129));
    T[C[0]] = k = 0;
    for (int j = 1; j < N; j++) {
      if (B[C[j]] != B[C[j - 1]])
        k++;
      else if (C[j] + i < N && N <= C[j - 1] + i)
        k++;
      else if (C[j] + i < N && C[j - 1] + i < N &&
               B[C[j] + i] != B[C[j - 1] + i])
        k++;
      T[C[j]] = k;
    }
    for (int j = 0; j < N; j++) B[j] = T[j];
  }
}
void LCP(string &S, vector<int> &C, vector<int> &lcp, int N) {
  vector<int> rnk(N);
  for (int i = 0; i < N; i++) rnk[C[i]] = i;
  lcp.resize(N);
  for (int i = 0, h = 0; i < N; i++) {
    if (rnk[i]) {
      while (i + h < N && C[rnk[i] - 1] + h < N &&
             S[i + h] == S[C[rnk[i] - 1] + h])
        h++;
      lcp[rnk[i]] = h;
    }
    if (h) h--;
  }
}
string S;
int N;
vector<int> sa, lcp;
stack<pair<int, int> > st;
void main2() {
  cin >> S;
  N = S.size();
  suffixArray(S, sa, N);
  LCP(S, sa, lcp, N);
  while (!st.empty()) st.pop();
  long long ans = 1LL * N * (N + 1) / 2;
  lcp.push_back(0);
  for (int i = 1; i < N + 1; i++) {
    int cnt = 0;
    while (!st.empty() && st.top().first > lcp[i]) {
      pair<int, int> t = st.top();
      st.pop();
      int d;
      if (st.empty()) {
        d = t.first - lcp[i];
        cnt += t.second;
      } else {
        if (st.top().first > lcp[i]) {
          d = t.first - st.top().first;
          st.top().second += t.second;
        } else {
          d = t.first - lcp[i];
          cnt += t.second;
        }
      }
      ans -= 1LL * d * (t.second + 1);
      ans += 1LL * d * (t.second + 1) * (t.second + 1);
    }
    st.push(pair<int, int>(lcp[i], cnt + 1));
  }
  cout << ans << endl;
}
int TC;
int main() {
  scanf("%d", &TC);
  while (TC--) main2();
}