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

public class CF802I {
	final int ALPHA = 26;
	final int OFFSET = 'a';
	int next, MAX, last, len[], link[], trie[][];
	long[] dp;
	boolean[] terminal;
	void suffixAutomaton(char[] s) {
		MAX = s.length << 1;
		next = 1;  last = 0;
		len = new int[MAX];
		link = new int[MAX];
		trie = new int[ALPHA][MAX];
		terminal = new boolean[MAX];
		link[0] = -1;
		for(char cc : s) {
			int c = cc - OFFSET;
			int cur = next++;
			len[cur] = len[last] + 1;
			int p = last;
			while(p != -1 && trie[c][p] == 0) {
				trie[c][p] = cur;
				p = link[p];
			}
			if(p == -1) {
				link[cur] = 0;
			} else {
				int q = trie[c][p];
				if(len[p] + 1 == len[q]) {
					link[cur] = q;
				} else {
					int clone = next++;
					len[clone] = len[p] + 1;
					link[clone] = link[q];
					for(int i = 0 ; i < ALPHA ; i++)
						trie[i][clone] = trie[i][q];
					while(p != -1 && trie[c][p] == q) {
						trie[c][p] = clone;
						p = link[p];
					}
					link[q] = link[cur] = clone;
				}
			}
			last = cur;
		}
		terminal = new boolean[MAX];
		int p = last;
		while(p > 0) {
			terminal[p] = true;
			p = link[p];
		}
		dp = new long[MAX];
		dfs(0);
	}
	void dfs(int node) {
		if(dp[node] != 0) return;
		dp[node] = terminal[node] ? 1 : 0;
		for(int let = 0 ; let < ALPHA ; let++) {
			if(trie[let][node] != 0) {
				dfs(trie[let][node]);
				dp[node] += dp[trie[let][node]];
			}
		}
	}
	public CF802I() {
		FS scan = new FS();
		PrintWriter out = new PrintWriter(System.out);
		int t = scan.nextInt();
		for(int tt = 0 ; tt < t ; tt++) {
			char[] s = scan.next().toCharArray();
			suffixAutomaton(s);
			long res = 0;
			for(int node = 1 ; node < MAX ; node++)
				res += dp[node] * dp[node] * (len[node] - len[link[node]]);
			out.println(res);
		}
		out.close();
	}
	class FS {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer("");
		public String next() {
			while(!st.hasMoreTokens()) {
				try { st = new StringTokenizer(br.readLine()); }
				catch(Exception e) { e.printStackTrace(); }
			}
			return st.nextToken();
		}
		public int nextInt() { return Integer.parseInt(next()); }
	}
	public static void main(String[] args) { new CF802I(); }
}