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;
using db = double;
using ll = long long;
using uint = unsigned int;
using ull = unsigned long long;
using pii = pair<int, int>;
template <class T>
void cmax(T& x, const T& y) {
  if (x < y) x = y;
}
template <class T>
void cmin(T& x, const T& y) {
  if (x > y) x = y;
}
template <class T>
void sort(vector<T>& v) {
  sort(v.begin(), v.end());
}
template <class T>
void reverse(vector<T>& v) {
  reverse(v.begin(), v.end());
}
template <class T>
void unique(vector<T>& v) {
  sort(v.begin(), v.end()), v.erase(unique(v.begin(), v.end()), v.end());
}
inline void reverse(string& s) { reverse(s.begin(), s.end()); }
const int SZ = 1 << 23 | 233;
struct FILEIN {
  char qwq[SZ], *S = qwq, *T = qwq, ch;
  inline char GETC() {
    return (S == T) && (T = (S = qwq) + fread(qwq, 1, SZ, stdin), S == T)
               ? EOF
               : *S++;
  }
  inline FILEIN& operator>>(char& c) {
    while (isspace(c = GETC()))
      ;
    return *this;
  }
  inline FILEIN& operator>>(string& s) {
    s.clear();
    while (isspace(ch = GETC()))
      ;
    if (!~ch) return *this;
    s = ch;
    while (!isspace(ch = GETC()) && ~ch) s += ch;
    return *this;
  }
  inline FILEIN& operator>>(char* str) {
    char* cur = str;
    while (*cur) *cur++ = 0;
    cur = str;
    while (isspace(ch = GETC()))
      ;
    if (!~ch) return *this;
    *cur = ch;
    while (!isspace(ch = GETC()) && ~ch) *++cur = ch;
    *++cur = 0;
    return *this;
  }
  template <class T>
  inline void read(T& x) {
    bool f = 0;
    while ((ch = GETC()) < 48 && ~ch) f ^= (ch == 45);
    x = ~ch ? (ch ^ 48) : 0;
    while ((ch = GETC()) > 47) x = x * 10 + (ch ^ 48);
    x = f ? -x : x;
  }
  inline FILEIN& operator>>(int& x) { return read(x), *this; }
  inline FILEIN& operator>>(ll& x) { return read(x), *this; }
  inline FILEIN& operator>>(uint& x) { return read(x), *this; }
  inline FILEIN& operator>>(ull& x) { return read(x), *this; }
  inline FILEIN& operator>>(double& x) {
    read(x);
    bool f = x < 0;
    x = f ? -x : x;
    if (ch ^ '.') return *this;
    double d = 0.1;
    while ((ch = GETC()) > 47) x += d * (ch ^ 48), d *= .1;
    return x = f ? -x : x, *this;
  }
} in;
struct FILEOUT {
  const static int LIMIT = 1 << 22;
  char quq[SZ], ST[233];
  int sz, O, pw[233];
  FILEOUT() {
    set(7);
    for (register int i = (pw[0] = 1); i <= (9); ++i) pw[i] = pw[i - 1] * 10;
  }
  ~FILEOUT() { flush(); }
  inline void flush() { fwrite(quq, 1, O, stdout), fflush(stdout), O = 0; }
  inline FILEOUT& operator<<(char c) { return quq[O++] = c, *this; }
  inline FILEOUT& operator<<(string str) {
    if (O > LIMIT) flush();
    for (char c : str) quq[O++] = c;
    return *this;
  }
  inline FILEOUT& operator<<(char* str) {
    if (O > LIMIT) flush();
    char* cur = str;
    while (*cur) quq[O++] = (*cur++);
    return *this;
  }
  template <class T>
  void write(T x) {
    if (O > LIMIT) flush();
    if (x < 0) {
      quq[O++] = 45;
      x = -x;
    }
    do {
      ST[++sz] = x % 10 ^ 48;
      x /= 10;
    } while (x);
    while (sz) quq[O++] = ST[sz--];
  }
  inline FILEOUT& operator<<(int x) { return write(x), *this; }
  inline FILEOUT& operator<<(ll x) { return write(x), *this; }
  inline FILEOUT& operator<<(uint x) { return write(x), *this; }
  inline FILEOUT& operator<<(ull x) { return write(x), *this; }
  int len, lft, rig;
  void set(int l) { len = l; }
  inline FILEOUT& operator<<(double x) {
    bool f = x < 0;
    x = f ? -x : x, lft = x, rig = 1. * (x - lft) * pw[len];
    return write(f ? -lft : lft), quq[O++] = '.', write(rig), *this;
  }
} out;
struct Math {
  vector<long long> fac, inv;
  long long mod;
  void set(long long n, long long Mod) {
    fac.resize(n + 1), inv.resize(n + 1), mod = Mod;
    for (register long long i = (fac[0] = 1); i <= (n); ++i)
      fac[i] = fac[i - 1] * i % mod;
    inv[n] = qpow(fac[n], mod - 2);
    for (register long long i = (n - 1); i >= (0); --i)
      inv[i] = inv[i + 1] * (i + 1) % mod;
  }
  long long qpow(long long x, long long y) {
    long long ans = 1;
    for (; y; y >>= 1, x = x * x % mod)
      if (y & 1) ans = ans * x % mod;
    return ans;
  }
  long long C(long long n, long long m) {
    if (n < 0 || m < 0 || n < m) return 0;
    return fac[n] * inv[m] % mod * inv[n - m] % mod;
  }
  long long gcd(long long x, long long y) { return !y ? x : gcd(y, x % y); }
  long long lcm(long long x, long long y) { return x * y / gcd(x, y); }
} math;
long long ans = 0;
const long long maxn = 2e5 + 52;
struct suffix_auto_maton {
  long long ch[maxn][26], fa[maxn], len[maxn];
  long long las, cnt;
  suffix_auto_maton() { las = cnt = 1; }
  void init() {
    memset(ch, 0, sizeof(ch));
    memset(fa, 0, sizeof(fa));
    memset(len, 0, sizeof(len));
    memset(sz, 0, sizeof(sz));
    las = cnt = 1;
  }
  void ins(long long c) {
    long long p = las, np = las = ++cnt;
    len[np] = len[p] + 1, sz[np] = 1;
    for (; p && !ch[p][c]; p = fa[p]) ch[p][c] = np;
    if (!p) {
      fa[np] = 1;
    } else {
      long long q = ch[p][c];
      if (len[q] == len[p] + 1) {
        fa[np] = q;
      } else {
        long long nq = ++cnt;
        memcpy(ch[nq], ch[q], sizeof(ch[q]));
        fa[nq] = fa[q], fa[q] = fa[np] = nq, len[nq] = len[p] + 1;
        for (; p && ch[p][c] == q; p = fa[p]) ch[p][c] = nq;
      }
    }
  }
  long long sz[maxn];
  vector<long long> g[maxn];
  void dfs(long long u) {
    for (long long v : g[u]) {
      dfs(v);
      sz[u] += sz[v];
    }
  }
  void ins(char* s) {
    char* cur = s;
    while (*cur) ins((*cur++) - 'a');
  }
  void build() {
    for (long long i = 1; i <= cnt; i++) g[i].clear();
    for (long long i = 2; i <= cnt; i++) g[fa[i]].emplace_back(i);
    dfs(1);
  }
  void calc() {
    for (register long long i = (2); i <= (cnt); ++i)
      ans += sz[i] * sz[i] * (len[i] - len[fa[i]]);
  }
} sam;
char s[maxn];
signed main() {
  long long _;
  in >> _;
  while (_--) {
    in >> s;
    sam.init();
    sam.ins(s);
    sam.build();
    ans = 0;
    sam.calc();
    out << ans << '\n';
  }
  return 0;
}