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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.nio.charset.StandardCharsets;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.TreeMap;

public class SumOfSquares {
    public static void main(String[] args) throws IOException {
        in.nextToken();
        int tests = (int) in.nval;

        for (int T = 0; T < tests; T++) {
            LrsArray lrsArray = new LrsArray();

            Map<Integer, List<Integer>> repeats = new HashMap<>();

            in.nextToken();
            for (char c : in.sval.toCharArray()) {
                LrsArray.Lmo repeat = lrsArray.append(c);
                if (repeat.length > 0) {
                    addValue(repeats, repeat.rightEnd, lrsArray.text.size() - 1);
                } else {
                    addValue(repeats, 0, lrsArray.text.size() - 1);
                }
            }

            TreeMap<LrsArray.Lmo, Long> counts = new TreeMap<>();
            dfs(repeats, lrsArray.lrs, counts, 0);

            long sumOfSquares = 0;
            for (int i = 1; i < lrsArray.text.size(); i++) {
                LrsArray.Lmo lmo = lrsArray.lrs.get(i);

                sumOfSquares += i - lmo.length;
            }

            int lastEnd = 0;
            int lastLen = 0;
            for (Map.Entry<LrsArray.Lmo, Long> entry : counts.entrySet()) {
                LrsArray.Lmo lmo = entry.getKey();

                if (lastEnd != lmo.rightEnd) {
                    lastEnd = lmo.rightEnd;
                    lastLen = lmo.lrs().length;
                }

                long length = lmo.length - lastLen;
                sumOfSquares += length * square(entry.getValue() + 1) - length;

                lastLen = lmo.length;
            }

            out.println(sumOfSquares);
        }

        out.flush();
    }

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

    static long dfs(Map<Integer, List<Integer>> tree, List<LrsArray.Lmo> lrs, Map<LrsArray.Lmo, Long> counts, Integer node) {
        long result = 1;

        TreeMap<Integer, Long> sorted = new TreeMap<>();
        Map<Integer, LrsArray.Lmo> lmos = new HashMap<>();

        for (Integer child : tree.getOrDefault(node, Collections.emptyList())) {
            long value = dfs(tree, lrs, counts, child);

            sorted.merge(lrs.get(child).length, value, (x, y) -> x + y);
            lmos.put(lrs.get(child).length, lrs.get(child));
            result += value;
        }

        long count = 0;
        for (Map.Entry<Integer, Long> entry : sorted.descendingMap().entrySet()) {
            count += entry.getValue();
            counts.put(lmos.get(entry.getKey()), count);
        }

        return result;
    }

    static <K, V> void addValue(Map<K, List<V>> map, K key, V value) {
        if (!map.containsKey(key)) {
            map.put(key, new ArrayList<>());
        }
        map.get(key).add(value);
    }

    static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(
            System.in, StandardCharsets.ISO_8859_1
    )));

    static PrintWriter out = new PrintWriter(new OutputStreamWriter(
            System.out, StandardCharsets.ISO_8859_1
    ));
}

class LrsArray {
    List<Character> text = arrayList(null);

    Map<Pair<Lmo, Character>, Integer> extensions = new HashMap<>();

    List<Lmo> lrs = arrayList(new Lmo(-1, -1) {
        @Override
        boolean isNext(char c) {
            return true;
        }
    });

    Lmo append(char c) {
        text.add(c);

        Lmo longest = lrs.get(lrs.size() - 1);

        while (!longest.hasExtension(c)) {
            extensions.put(Pair.of(longest, c), lrs.size());
            longest = longest.lps();
        }

        longest = longest.extend(c);
        lrs.add(longest);

        return longest;
    }

    class Lmo implements Comparable<Lmo> {
        final int rightEnd;
        final int length;

        Lmo(int rightEnd, int length) {
            this.rightEnd = rightEnd;
            this.length = length;
        }

        boolean isNext(char c) {
            return text.get(rightEnd + 1) == c;
        }

        boolean hasExtension(char c) {
            return isNext(c) || extensions.containsKey(Pair.of(this, c));
        }

        Lmo extend(char c) {
            return new Lmo(
                    isNext(c)
                            ? rightEnd + 1
                            : extensions.get(Pair.of(this, c)),
                    length + 1
            );
        }

        Lmo lrs() {
            return lrs.get(rightEnd);
        }

        Lmo lps() {
            return length - 1 == lrs().length
                    ? lrs()
                    : new Lmo(rightEnd, length - 1);
        }

        @Override
        public int compareTo(LrsArray.Lmo o) {
            if (rightEnd == o.rightEnd) {
                return Integer.compare(length, o.length);
            } else {
                return Integer.compare(rightEnd, o.rightEnd);
            }
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Lmo lmo = (Lmo) o;
            return rightEnd == lmo.rightEnd &&
                    length == lmo.length;
        }

        @Override
        public int hashCode() {
            return Objects.hash(rightEnd, length);
        }

        @Override
        public String toString() {
            return rightEnd + " " + length;
        }
    }

    static <T> List<T> arrayList(T single) {
        ArrayList<T> arrayList = new ArrayList<>(1);
        arrayList.add(single);
        return arrayList;
    }
}

class Pair<T1, T2> {
    final T1 p1;
    final T2 p2;

    Pair(T1 p1, T2 p2) {
        this.p1 = p1;
        this.p2 = p2;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Pair<?, ?> pair = (Pair<?, ?>) o;
        return Objects.equals(p1, pair.p1) &&
                Objects.equals(p2, pair.p2);
    }

    @Override
    public int hashCode() {
        return Objects.hash(p1, p2);
    }

    static <T1, T2> Pair<T1, T2> of(T1 p1, T2 p2) {
        return new Pair<>(p1, p2);
    }
}