E. String Strange Sum
time limit per test
4 seconds
memory limit per test
512 mebibytes
input
standard input
output
standard output

You are given a string $$$s$$$ consisting of lowercase English letters.

Let us consider a segment $$$[\ell, r]$$$ such that $$$2 \leq \ell \leq r \leq |s|$$$. Let us define $$$f(\ell, r)$$$ as the length of the longest suffix of substring $$$s[1, \ell-1]$$$ such that this suffix can be divided into prefixes of substring $$$s[\ell, r]$$$. If there are no such suffixes then $$$f(\ell, r) = 0$$$.

Find the sum $$$\displaystyle \sum\limits_{\ell=2}^{|s|} \sum\limits_{r=\ell}^{|s|} f(\ell, r)$$$.

Input

The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^5$$$) — the number of test cases. Description of test cases follows.

The only line for each test case contains the string $$$s$$$ ($$$2 \leq |s| \leq 2 \cdot 10^5$$$) consisting of lowercase English letters.

It is guaranteed that the sum of $$$|s|$$$ for all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, print a single integer — the answer to the problem.

Example
Input
8
aa
ab
ababa
abaaba
abacaba
abaaababaab
aababcabcbc
abcdabcabaabcd
Output
1
0
6
7
0
74
51
20
Note

Let us consider the third test case. In this case, $$$f(2, 2) = 0$$$, $$$f(2, 3) = 0$$$, $$$f(2, 4) = 0$$$, $$$f(2, 5) = 0$$$, $$$f(3, 3) = 0$$$, $$$f(3, 4) = 2$$$, $$$f(3, 5) = 2$$$, $$$f(4, 4) = 0$$$, $$$f(4, 5) = 2$$$, $$$f(5, 5) = 0$$$. So the answer is $$$6$$$.