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.math.BigInteger;
import java.util.*;
import java.io.*;

public class Main {

    public static InputReader in = new InputReader(System.in);
    public static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args)
    {
        int a;
        String s;
        SAM part=new SAM();
        a=in.nextInt();
        while (a--!=0)
        {
            s=in.next();
            part.init(2*s.length()+2,26);
            for(int i=0;i<s.length();++i)
                part.insert(s.charAt(i)-'a');
            long ans=0;
            part.topo();
            SAM_node part2=part.root;
            for(int i=0;i<s.length();++i)
            {
                part2=part2.next[s.charAt(i)-'a'];
                part2.cnt=1;
            }
            for(int i=part.cur-1;i>0;--i)
                part.pool[i].pre.cnt+=part.pool[i].cnt;
            for(int i=part.cur-1;i>0;--i)
                ans+=(long)part.pool[i].cnt*(long)part.pool[i].cnt*((long)part.pool[i].step-(long)part.pool[i].pre.step);
            out.println(ans);
        }
        out.flush();
        out.close();
    }
}
class SAM_node
{
    SAM_node pre,next[];
    int step,cnt;
    SAM_node(int sigma)
    {
        next=new SAM_node[sigma];
        Arrays.fill(next,null);
        step=0;
        cnt=0;
        pre=null;
    }
}
class SAM
{
    SAM_node SAM_pool[],root,last;
    int d[];
    SAM_node pool[];
    int cur;
    int sigma;
    void topo() {
        int cnt = cur;
        int maxVal = 0;
        Arrays.fill(d, 0);
        for (int i = 1; i < cnt; i++) {
            maxVal = Math.max(maxVal, SAM_pool[i].step);

        d[SAM_pool[i].step]++;
    }
        for (int i = 1; i <= maxVal; i++)
            d[i] += d[i - 1];
        for (int i = 1; i < cnt; i++)
            pool[d[SAM_pool[i].step]--] = SAM_pool[i];
        pool[0] = root;
    }
    void init(int a,int b)
    {
        d=new int[a];
        pool=new SAM_node[a];
        SAM_pool=new SAM_node[a];
        SAM_pool[0]=new SAM_node(b);
        sigma=b;
        root=last=SAM_pool[0];
        cur=1;
    }
    void insert(int w)
    {
        SAM_node p=last;
        SAM_pool[cur]=new SAM_node(sigma);
        SAM_node np=SAM_pool[cur];
        last=np;
        cur++;
        np.step=p.step+1;
        while (p!=null && p.next[w]==null)
        {
            p.next[w]=np;
            p = p.pre;
        }
        if(p==null)
        {
            np.pre=root;
        }
        else
        {
            SAM_node q=p.next[w];
            if(p.step+1==q.step)
                np.pre=q;
            else {
                SAM_node nq = SAM_pool[cur++] = new SAM_node(sigma);
                nq.next = Arrays.copyOf(q.next, sigma);
                nq.cnt = q.cnt;
                nq.step = p.step + 1;
                nq.pre = q.pre;
                q.pre = nq;
                np.pre = nq;
                while (p != null && p.next[w]==(q)) {
                    p.next[w] = nq;
                    p = p.pre;
                }
            }
        }
    }
}
class InputReader{
    private final static int BUF_SZ = 65536;
    BufferedReader in;
    StringTokenizer tokenizer;
    public InputReader(InputStream in) {
        super();
        this.in = new BufferedReader(new InputStreamReader(in),BUF_SZ);
        tokenizer = new StringTokenizer("");
    }
    public String next() {
        while (!tokenizer.hasMoreTokens()) {
            try {
                tokenizer = new StringTokenizer(in.readLine());
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return tokenizer.nextToken();
    }
    public int nextInt() {
        return Integer.parseInt(next());
    }
    public long nextLong()
    {
        return Long.parseLong(next());
    }
}