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 JAVA):

Solution:
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.util.Random;
import java.util.InputMismatchException;
import java.util.HashMap;
import java.util.Deque;
import java.util.function.Function;
import java.util.ArrayList;
import java.util.Map;
import java.io.OutputStreamWriter;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.PrintStream;
import java.io.BufferedWriter;
import java.util.Collection;
import java.io.IOException;
import java.util.List;
import java.io.Writer;
import java.util.Map.Entry;
import java.util.ArrayDeque;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Rustam Musin (t.me/musin_acm)
 */
public class Main {
  public static void main(String[] args) {
    InputStream inputStream = System.in;
    OutputStream outputStream = System.out;
    InputReader in = new InputReader(inputStream);
    OutputWriter out = new OutputWriter(outputStream);
    ILozhnieNovostiSlozhnaya solver = new ILozhnieNovostiSlozhnaya();
    solver.solve(1, in, out);
    out.close();
  }

  static class ILozhnieNovostiSlozhnaya {
    public void solve(int testNumber, InputReader in, OutputWriter out) {
      if (false) {
        new ILozhnieNovostiSlozhnaya.Tester().test();
        return;
      }
      int t = in.readInt();
      while (t-- > 0) {
        String s = in.next();
        long answer = new ILozhnieNovostiSlozhnaya.Solver3(s).solve();
        out.printLine(answer);
      }
    }

    static long sq(long x) {
      return x * x;
    }

    static class Naive {
      String s;

      Naive(String s) {
        this.s = s;
      }

      long solve() {
        Map<String, Integer> subs = new HashMap<>();
        for (int i = 0; i < s.length(); i++)
          for (int j = i + 1; j <= s.length(); j++) subs.merge(s.substring(i, j), 1, Integer::sum);
        long ans = 0;
        for (Map.Entry<String, Integer> e : subs.entrySet()) {
          ans += sq(e.getValue());
        }
        return ans;
      }

    }

    static class Tester {
      Random rnd = new Random(239);

      String randomString(int n, int m) {
        char[] s = new char[n];
        for (int i = 0; i < n; i++) s[i] = (char) ('a' + rnd.nextInt(m));
        return new String(s);
      }

      void test() {
        for (int t = 0; ; t++) {
          String s = randomString(rnd.nextInt(10) + 1, 5);
          long naive = new ILozhnieNovostiSlozhnaya.Naive(s).solve();
          long solve = new ILozhnieNovostiSlozhnaya.Solver3(s).solve();
          if (naive != solve) {
            System.err.println(s);
            System.err.println(naive);
            System.err.println(solve);
            return;
          }
        }
      }

    }

    static class Solver3 {
      int n;
      ILozhnieNovostiSlozhnaya.SuffixArray sa;

      Solver3(String s) {
        sa = new ILozhnieNovostiSlozhnaya.SuffixArray((s + "$").toCharArray());
        n = s.length() + 1;
      }

      <T> void countSort(T[] a, Function<T, Integer> f) {
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for (T x : a) {
          int r = f.apply(x);
          min = Math.min(min, r);
          max = Math.max(max, r);
        }
        int[] count = new int[max - min + 1];
        for (T x : a) count[f.apply(x) - min]++;
        for (int i = 0, j = 0; i < count.length; i++) {
          int x = count[i];
          count[i] = j;
          j += x;
        }
        T[] res = (T[]) new Object[a.length];
        for (T x : a) res[count[f.apply(x) - min]++] = x;
        System.arraycopy(res, 0, a, 0, res.length);
      }

      int[] reversed(int[] a) {
        int n = a.length;
        int[] res = new int[n];
        for (int i = 0; i < n; i++) res[i] = a[n - i - 1];
        return res;
      }

      int[] getRightBorders(int[] a) {
        Deque<Integer> q = new ArrayDeque<>();
        int n = a.length;
        int[] res = new int[n];
        for (int i = n - 1; i >= 0; i--) {
          while (!q.isEmpty() && a[q.peekLast()] >= a[i]) q.pollLast();
          res[i] = !q.isEmpty() ? (q.peekLast() - 1) : (n - 1);
          q.addLast(i);
        }
        return res;
      }

      int[] getLeftBorders(int[] a) {
        int[] res = reversed(getRightBorders(reversed(a)));
        int n = a.length;
        for (int i = 0; i < res.length; i++) res[i] = n - 1 - res[i];
        return res;
      }

      long solve() {
        long ans1 = solveForLcp(sa.lcp);
        long ans2 = 0;
        for (int i = 0; i < n; i++) {
          int h = n - 1 - sa.order[i];
          h -= Math.max(
              sa.lcp[i],
              i + 1 == n ? 0 : sa.lcp[i + 1]
          );
          if (h > 0) ans2 += h;
        }
        return ans1 + ans2;
      }

      long solveForLcp(int[] lcp) {
        int[] right = getRightBorders(lcp);
        int[] left = getLeftBorders(lcp);
        int n = lcp.length;
        ILozhnieNovostiSlozhnaya.Solver3.Node[] a = new ILozhnieNovostiSlozhnaya.Solver3.Node[n];
        for (int i = 0; i < n; i++) a[i] = new ILozhnieNovostiSlozhnaya.Solver3.Node(left[i], right[i], lcp[i]);
        countSort(a, x -> x.height);
        countSort(a, x -> x.left);
        List<ILozhnieNovostiSlozhnaya.Solver3.Node>[] byLeft = new List[n];
        for (int i = 0; i < n; i++) byLeft[i] = new ArrayList<>();
        for (ILozhnieNovostiSlozhnaya.Solver3.Node x : a) byLeft[x.left].add(x);
        long result = 0;
        Deque<ILozhnieNovostiSlozhnaya.Solver3.Node> q = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
          for (int j = 0; j < byLeft[i].size(); j++) {
            ILozhnieNovostiSlozhnaya.Solver3.Node cur = byLeft[i].get(j);
            while (!q.isEmpty() && q.peekLast().right < cur.left) q.pollLast();
            int deltaHeight = cur.height - (q.isEmpty() ? 0 : q.peekLast().height);
            q.addLast(cur);
            result += deltaHeight * sq(cur.right - cur.left + 2);
            while (j + 1 < byLeft[i].size() && byLeft[i].get(j + 1).height == cur.height) j++;
          }
        }
        return result;
      }

      static class Node {
        int left;
        int right;
        int height;

        public Node(int left, int right, int height) {
          this.left = left;
          this.right = right;
          this.height = height;
        }

        public String toString() {
          return "Node{" +
              "left=" + left +
              ", right=" + right +
              ", height=" + height +
              '}';
        }

      }

    }

    static class SuffixArray {
      int n;
      char[] s;
      int[] order;
      int[] type;
      int[] lcp;

      SuffixArray(char[] s) {
        this.s = s;
        this.n = s.length;
        initSuffixArray();
        initLCP();
//      print();
      }

      void initLCP() {
        lcp = new int[n];
        for (int i = 0, k = 0; i < n - 1; i++) {
          int pi = type[i];
          int j = order[pi - 1];
          while (s[i + k] == s[j + k]) k++;
          lcp[pi] = k;
          if (k > 0) k--;
        }
//      lcpST = new SparseTable(lcp);
      }

      void countSort(int countSize) {
        int[] count = new int[countSize];
        for (int t : type) count[t]++;
        for (int i = 0, j = 0; i < countSize; i++) {
          int x = count[i];
          count[i] = j;
          j += x;
        }
        int[] order2 = new int[n];
        for (int x : order) order2[count[type[x]]++] = x;
        System.arraycopy(order2, 0, order, 0, n);
      }

      void initSuffixArray() {
        order = new int[n];
        type = new int[n];
        {
          for (int i = 0; i < n; i++) order[i] = i;
          for (int i = 0; i < n; i++) type[i] = s[i];
          countSort(1 << 8);
          type[order[0]] = 0;
          for (int i = 1, j = 0; i < n; i++) {
            if (s[order[i]] != s[order[i - 1]]) j++;
            type[order[i]] = j;
          }
        }
        for (int len = 1; len < n; len <<= 1) {
          for (int i = 0; i < n; i++) order[i] = (order[i] - len + n) % n;
          countSort(n);
          int[] type2 = new int[n];
          type2[order[0]] = 0;
          for (int i = 1, j = 0; i < n; i++) {
            int left1 = type[order[i]];
            int left2 = type[order[i - 1]];
            int right1 = type[(order[i] + len) % n];
            int right2 = type[(order[i - 1] + len) % n];
            if (left1 != left2 || right1 != right2) j++;
            type2[order[i]] = j;
          }
          System.arraycopy(type2, 0, type, 0, n);
        }
      }

    }

  }

  static class InputReader {
    private InputStream stream;
    private byte[] buf = new byte[1024];
    private int curChar;
    private int numChars;
    private InputReader.SpaceCharFilter filter;

    public InputReader(InputStream stream) {
      this.stream = stream;
    }

    public int read() {
      if (numChars == -1) {
        throw new InputMismatchException();
      }
      if (curChar >= numChars) {
        curChar = 0;
        try {
          numChars = stream.read(buf);
        } catch (IOException e) {
          throw new InputMismatchException();
        }
        if (numChars <= 0) {
          return -1;
        }
      }
      return buf[curChar++];
    }

    public int readInt() {
      int c = read();
      while (isSpaceChar(c)) {
        c = read();
      }
      int sgn = 1;
      if (c == '-') {
        sgn = -1;
        c = read();
      }
      int res = 0;
      do {
        if (c < '0' || c > '9') {
          throw new InputMismatchException();
        }
        res *= 10;
        res += c - '0';
        c = read();
      } while (!isSpaceChar(c));
      return res * sgn;
    }

    public String readString() {
      int c = read();
      while (isSpaceChar(c)) {
        c = read();
      }
      StringBuilder res = new StringBuilder();
      do {
        if (Character.isValidCodePoint(c)) {
          res.appendCodePoint(c);
        }
        c = read();
      } while (!isSpaceChar(c));
      return res.toString();
    }

    public boolean isSpaceChar(int c) {
      if (filter != null) {
        return filter.isSpaceChar(c);
      }
      return isWhitespace(c);
    }

    public static boolean isWhitespace(int c) {
      return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
    }

    public String next() {
      return readString();
    }

    public interface SpaceCharFilter {
      public boolean isSpaceChar(int ch);

    }

  }

  static class OutputWriter {
    private final PrintWriter writer;

    public OutputWriter(OutputStream outputStream) {
      writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
    }

    public OutputWriter(Writer writer) {
      this.writer = new PrintWriter(writer);
    }

    public void close() {
      writer.close();
    }

    public void printLine(long i) {
      writer.println(i);
    }

  }
}