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:
//Created by Aminul on 9/3/2019.

import java.io.*;
import java.util.*;

import static java.lang.Math.max;

public class CF802I_fast {
    public static void main(String[] args) throws Exception {
        FastReader in = new FastReader(System.in);
        PrintWriter pw = new PrintWriter(System.out);
        int test = in.nextInt();
        for(int t = 1; t <= test; t++) {
            char[] s = in.next().toCharArray();
            int n = s.length;
            int sa[] = suffixArray(s);
            final int lcp[] = lcp(sa, s);
            long ans = 0;

            SegTree segTree = new SegTree(n + 1);
            for (int i = n - 1; i >= 0; i--) {
                int len = n - sa[i];
                ans += segTree.query(1, len) + len;
                segTree.clearRange(lcp[i] + 1, n);
                segTree.update(1, lcp[i], 1);
            }

            segTree = new SegTree(n + 1);
            for (int i = 0; i < n; i++) {
                int len = n - sa[i];
                ans += segTree.query(1, len);
                if(i + 1 < n) segTree.clearRange(lcp[i + 1] + 1, n);
                if(i + 1 < n) segTree.update(1, lcp[i + 1], 1);
            }

            pw.println(ans);
        }
        pw.close();
    }

    static int[] suffixArray(char[] S) {
        int n = S.length;
        Integer ord[] = new Integer[n];
        for (int i = 0; i < n; i++) ord[i] = n - 1 - i;
        Arrays.sort(ord, (a, b) -> Character.compare(S[a], S[b]));
        int order[] = new int[n];
        for (int i = 0; i < n; i++) order[i] = ord[i];
        //Arrays.sort(order, new Comparator<Integer>() {public int compare(Integer o1, Integer o2) { return S[o1] - S[o2]; }});
        int[] sa = new int[n];
        int[] classes = new int[n];
        for (int i = 0; i < n; i++) {
            sa[i] = order[i];
            classes[i] = S[i];
        }
        for (int len = 1; len < n; len <<= 1) {
            int[] c = classes.clone();
            for (int i = 0; i < n; i++) {
                classes[sa[i]] = i > 0 && c[sa[i - 1]] == c[sa[i]] && sa[i - 1] + len < n
                        && c[sa[i - 1] + (len >> 1)] == c[sa[i] + (len >> 1)] ? classes[sa[i - 1]] : i;
            }
            int[] cnt = new int[n];
            for (int i = 0; i < n; i++) {
                cnt[i] = i;
            }
            int[] s = sa.clone();
            for (int i = 0; i < n; i++) {
                int s1 = s[i] - len;
                if (s1 >= 0) {
                    sa[cnt[classes[s1]]++] = s1;
                }
            }
        }
        return sa;
    }

    static int[] lcp(int[] sa, char[] s) {
        int n = sa.length;
        int[] rank = new int[n];
        for (int i = 0; i < n; i++)
            rank[sa[i]] = i;
        int[] lcp = new int[n];

        for (int i = 0, h = 0; i < n; i++) {
            if (rank[i] < n - 1) {
                for (int j = sa[rank[i] + 1]; max(i, j) + h < s.length
                        && s[i + h] == s[j + h]; ++h)
                    ;
                lcp[rank[i] + 1] = h;
                if (h > 0)
                    --h;
            }
        }
        return lcp;
    }



    static void debug(Object... obj) {
        System.err.println(Arrays.deepToString(obj));
    }

    static class SegTree {
        Node root;
        int n;

        SegTree(int N) {
            n = N;
            root = new Node();
        }

        void pushDown(Node node, int s, int m, int e) {
            if (node.lazy == 0) return;
            if (node.left != null) {
                node.left.value += (m - s + 1) * node.lazy;
                node.left.lazy += node.lazy;
            }
            if (node.right != null) {
                node.right.value += (e - m) * node.lazy;
                node.right.lazy += node.lazy;
            }
            node.lazy = 0;
        }

        void update(int l, int r, int v) {
            update(root, 1, n, l, r, v);
        }

        void update(Node node, int s, int e, int a, int b, int value) {
            if (s > e || s > b || e < a) return;
            if (s >= a && e <= b) {
                node.lazy += value;
                node.value += (e - s + 1) * value;
                return;
            }
            int m = (s + e) / 2;
            if (node.left == null) node.left = new Node();
            if (node.right == null) node.right = new Node();
            pushDown(node, s, m, e);
            update(node.left, s, m, a, b, value);
            update(node.right, m + 1, e, a, b, value);
            node.value = node.left.value + node.right.value;
        }

        void clearRange(int l, int r) {
            root = clearRange(root, 1, n, l, r);
        }

        Node clearRange(Node node, int s, int e, int a, int b) {
            if (s > e || s > b || e < a) return node;
            if (s >= a && e <= b) {
                return new Node();
            }
            int m = (s + e) / 2;
            if (node.left == null) node.left = new Node();
            if (node.right == null) node.right = new Node();
            pushDown(node, s, m, e);
            node.left = clearRange(node.left, s, m, a, b);
            node.right = clearRange(node.right, m + 1, e, a, b);
            node.value = node.left.value + node.right.value;
            return node;
        }

        long query(int l, int r) {
            return query(root, 1, n, l, r);
        }

        long query(Node node, int s, int e, int a, int b) {
            if (s > e || s > b || e < a) return 0;
            if (s >= a && e <= b) {
                return node.value;
            }
            int m = (s + e) / 2;
            if (node.left == null) node.left = new Node();
            if (node.right == null) node.right = new Node();
            pushDown(node, s, m, e);
            return query(node.left, s, m, a, b) + query(node.right, m + 1, e, a, b);
        }

        static class Node {
            Node left, right;
            long value, lazy;

            Node() {
            }

            Node(int v) {
                value = v;
            }

            @Override
            public String toString() {
                return "[" + value + ", " + lazy + "]";
            }
        }
    }
    
    static class FastReader {
        InputStream is;
        private byte[] inbuf = new byte[1024];
        private int lenbuf = 0, ptrbuf = 0;
    
        public FastReader(InputStream is) {
            this.is = is;
        }
    
        public int readByte() {
            if (lenbuf == -1) throw new InputMismatchException();
            if (ptrbuf >= lenbuf) {
                ptrbuf = 0;
                try {
                    lenbuf = is.read(inbuf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (lenbuf <= 0) return -1;
            }
            return inbuf[ptrbuf++];
        }
    
        public boolean isSpaceChar(int c) {
            return !(c >= 33 && c <= 126);
        }
        private boolean isEndOfLine(int c) {
            return c == '\n' || c == '\r' || c == -1;
        }
    
        public int skip() {
            int b;
            while ((b = readByte()) != -1 && isSpaceChar(b)) ;
            return b;
        }
    
        public String next() {
            int b = skip();
            StringBuilder sb = new StringBuilder();
            while (!(isSpaceChar(b))) {
                sb.appendCodePoint(b);
                b = readByte();
            }
            return sb.toString();
        }
    
    
    
        public String nextLine() {
            int c = skip();
            StringBuilder sb = new StringBuilder();
            while (!isEndOfLine(c)){
                sb.appendCodePoint(c);
                c = readByte();
            }
            return sb.toString();
        }
    
        public int nextInt() {
            int num = 0, b;
            boolean minus = false;
            while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')) ;
            if (b == '-') {
                minus = true;
                b = readByte();
            }
            while (true) {
                if (b >= '0' && b <= '9') {
                    num = (num << 3) + (num << 1) + (b - '0');
                } else {
                    return minus ? -num : num;
                }
                b = readByte();
            }
        }
    
        public long nextLong() {
            long num = 0;
            int b;
            boolean minus = false;
            while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')) ;
            if (b == '-') {
                minus = true;
                b = readByte();
            }
    
            while (true) {
                if (b >= '0' && b <= '9') {
                    num = (num << 3) + (num << 1) + (b - '0');
                } else {
                    return minus ? -num : num;
                }
                b = readByte();
            }
        }
    
        public double nextDouble() {
            return Double.parseDouble(next());
        }
    
        public char[] next(int n) {
            char[] buf = new char[n];
            int b = skip(), p = 0;
            while (p < n && !(isSpaceChar(b))) {
                buf[p++] = (char) b;
                b = readByte();
            }
            return n == p ? buf : Arrays.copyOf(buf, p);
        }
    
        public char readChar() {
            return (char) skip();
        }
    }
}