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 = 1e5 + 5;
pair<pair<int, int>, int> x[N];
int n, rnk[N], rev[N];
vector<int> pos[N];
set<int> st;
char s[N];
inline long long get(int x) { return 1LL * x * x; }
inline void set_rank() {
  sort(x, x + n);
  for (int i = 1, cur = 0; i < n; i++)
    rnk[x[i].second] = cur += x[i].first != x[i - 1].first;
}
inline void build_suffix_array() {
  for (int i = 0; i < n; i++) x[i] = {{s[i], rnk[i] = 0}, i};
  set_rank();
  for (int i = 0; n >> i; i++) {
    for (int j = 0; j < n; j++)
      x[j] = {{rnk[j], j + (1 << i) < n ? rnk[j + (1 << i)] : -1}, j};
    set_rank();
  }
}
inline void build_lcp_array() {
  for (int i = rnk[n] = n; ~i; i--) rev[rnk[i]] = i;
  for (int i = 0, cur = 0; i < n; i++) {
    while (s[i + cur] == s[rev[rnk[i] + 1] + cur]) cur++;
    if (cur) pos[cur--].push_back(rnk[i]);
  }
}
inline void read_input() {
  cin >> s;
  n = strlen(s);
}
inline void solve() {
  build_suffix_array();
  build_lcp_array();
}
inline void write_output() {
  long long ans = 0, cur = 0;
  for (int i = n; i; i--) st.insert(i);
  for (int i = n; i; i--) {
    for (auto p : pos[i]) {
      auto r = st.upper_bound(p), l = r++, mid = l--;
      cur -= get(*mid - *l) + get(*r - *mid);
      cur += get(*r - *l), st.erase(mid);
    }
    pos[i].clear(), ans += ++cur;
  }
  cout << ans << endl;
}
inline void test_cases() {
  int t;
  cin >> t;
  st.insert(0);
  while (t--) {
    read_input();
    solve();
    write_output();
  }
}
int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  test_cases();
  return 0;
}