시간 제한메모리 제한제출정답맞힌 사람정답 비율
4 초 (추가 시간 없음) 1024 MB11119.091%

문제

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)$.

입력

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$.

출력

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

예제 입력 1

8
aa
ab
ababa
abaaba
abacaba
abaaababaab
aababcabcbc
abcdabcabaabcd

예제 출력 1

1
0
6
7
0
74
51
20

노트

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$.