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 static java.util.Arrays.* ;

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

public class Main
{
    void main() throws Exception
    {
        Scanner sc = new Scanner(System.in) ;
        PrintWriter out = new PrintWriter(System.out) ;
        int TC = sc.nextInt() ;
        while(TC-->0) {
            char[] s = sc.next().toCharArray();
            SuffixAutomaton sa = new SuffixAutomaton(s);
            long ans = 0 ;
            for(int v = 1 ; v <= sa.idx ; v++)
                ans += (1L * sa.cnt[v] * sa.cnt[v]) * (sa.len[v] - sa.len[sa.link[v]]) ;
            out.println(ans);
        }
        out.flush();
        out.close();
    }
    class SuffixAutomaton
    {
        int[] link, len , cnt;
        int [][] next ;
        int lst, idx;
        
        SuffixAutomaton(char[] s)
        {
            int n = s.length;
            link = new int[n<<1];
            len = new int[n<<1];
            next = new int [26][n << 1] ;
            cnt = new int [n << 1] ;
            
            for(char c: s)
                addLetter(c - 'a');
            Integer [] id = new Integer[idx + 1] ;

            for(int i = 0 ; i <= idx ; i++)
                id[i] = i;
            
            sort(id , (x , y)->len[y] - len[x]);

            for(int v : id)
                cnt[link[v]] += cnt[v] ;
        }

        void addLetter(int c )
        {
            int cur = ++idx, p = lst;
            while(next[c][p] == 0) { next[c][p] = cur; p = link[p]; }
            cnt[cur] = 1 ;
            int q = next[c][p];
            if(q != cur)
                if(len[q] == len[p] + 1)
                    link[cur] = q;
                else
                {
                    int clone = ++idx;
                    len[clone] = len[p] + 1;
                    link[clone] = link[q];
                    for(int i = 0 ; i < 26 ; i++)
                        next[i][clone] = next[i][q] ;
                    link[cur] = link[q] = clone;
                    while(next[c][p] == q) { next[c][p] =  clone; p = link[p]; }
                }
            len[cur] = len[lst] + 1;
            lst = cur;
        }
    }

    class Scanner
    {
        BufferedReader br;
        StringTokenizer st;

        Scanner(InputStream in)
        {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        Scanner(String path) throws Exception
        {
            br = new BufferedReader(new FileReader(path)) ;
        }
        String next() throws Exception
        {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }
        int nextInt() throws Exception { return Integer.parseInt(next()); }

        long nextLong() throws Exception { return Long.parseLong(next()); }

        double nextDouble() throws Exception { return Double.parseDouble(next());}
    }

    public static void main (String [] args) throws Exception {(new Main()).main();}

}