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;
long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }
const int MAXLEN = 100000;
char s[MAXLEN + 2];
int n;
typedef struct Node {
  int start, end;
  int childs[27];
  int suffix;
  int nleafs;
  Node(int start, int end) : start(start), end(end) {
    memset(childs, -1, sizeof(childs));
    suffix = -1;
  }
} Node;
vector<Node> nodes;
int addnode(int start, int end) {
  nodes.push_back(Node(start, end));
  return ((int)(nodes).size()) - 1;
}
int build() {
  int root = addnode(0, 0);
  int atnode = root, atedge = 0, atlen = 0, rem = 0, prev = -1;
  for (int i = 0; i < n; ++i) {
    ++rem;
    prev = -1;
    while (rem > 0) {
      int tonode = nodes[atnode].childs[s[atedge] - 'a'];
      int tostart = tonode == -1 ? -1 : nodes[tonode].start;
      if (tonode != -1 && nodes[tonode].start + atlen >= nodes[tonode].end) {
        atedge += nodes[tonode].end - nodes[tonode].start;
        atlen -= nodes[tonode].end - nodes[tonode].start;
        atnode = tonode;
        continue;
      }
      if (tonode == -1) {
        int leaf = addnode(i, n);
        nodes[atnode].childs[s[atedge] - 'a'] = leaf;
        if (prev != -1) nodes[prev].suffix = atnode;
        prev = atnode;
      } else if (s[tostart + atlen] == s[i]) {
        ++atlen;
        if (prev != -1) nodes[prev].suffix = atnode;
        prev = atnode;
        break;
      } else {
        int branch = addnode(tostart, tostart + atlen);
        nodes[tonode].start += atlen;
        int leaf = addnode(i, n);
        nodes[atnode].childs[s[atedge] - 'a'] = branch;
        nodes[branch].childs[s[tostart + atlen] - 'a'] = tonode;
        nodes[branch].childs[s[i] - 'a'] = leaf;
        if (prev != -1) nodes[prev].suffix = branch;
        prev = branch;
      }
      --rem;
      if (atnode == root) {
        if (atlen > 0) --atlen;
        atedge++;
      } else {
        atnode = nodes[atnode].suffix;
      }
    }
  }
  return root;
}
void print(int node, int depth) {
  for (int i = 0; i < depth; ++i) printf("  ");
  printf("'");
  for (int i = nodes[node].start; i < nodes[node].end; ++i) printf("%c", s[i]);
  printf("'");
  if (nodes[node].end != n) printf(" -> %d", node);
  if (nodes[node].suffix != -1) printf(" [%d]", nodes[node].suffix);
  puts("");
  for (int i = 0; i < 27; ++i)
    if (nodes[node].childs[i] != -1) print(nodes[node].childs[i], depth + 1);
}
long long dfs(int at) {
  long long ret = 0;
  nodes[at].nleafs = 0;
  for (int i = (0); i < (27); ++i)
    if (nodes[at].childs[i] != -1) {
      int to = nodes[at].childs[i];
      ret += dfs(to);
      nodes[at].nleafs += nodes[to].nleafs;
    }
  int times = nodes[at].end - nodes[at].start;
  if (nodes[at].nleafs == 0) --times;
  if (nodes[at].nleafs == 0) nodes[at].nleafs = 1;
  ret += (long long)times * nodes[at].nleafs * nodes[at].nleafs;
  return ret;
}
void run() {
  scanf("%s", s);
  n = strlen(s);
  s[n] = '{';
  ++n;
  nodes.clear();
  int root = build();
  long long ret = dfs(0);
  printf("%lld\n", ret);
}
int main() {
  int n;
  scanf("%d", &n);
  for (int i = (1); i <= (n); ++i) run();
  return 0;
}