문자열 이상한 합

소문자 영어 알파벳으로 이루어진 문자열 $s$가 주어진다.

$2 \leq \ell \leq r \leq |s|$를 만족하는 구간 $[\ell, r]$을 생각하자. $f(\ell, r)$은 $s[1, \ell-1]$의 접미사 중에서, $s[\ell, r]$의 접두사들로 나눌 수 있는 가장 긴 접미사의 길이이다. 그런 접미사가 없으면 $f(\ell, r) = 0$이다.

다음 값을 구하라.

$\sum_{\ell=2}^{|s|} \sum_{r=\ell}^{|s|} f(\ell, r)$

첫 번째 줄에 테스트 케이스의 개수 $t$ ($1 \leq t \leq 10^5$)가 주어진다. 이어지는 $t$개의 줄에는 각각 소문자 영어 알파벳으로 이루어진 문자열 $s$ ($2 \leq |s| \leq 2 \cdot 10^5$)가 주어진다. 모든 테스트 케이스의 $|s|$ 합은 $2 \cdot 10^5$을 넘지 않는다.

각 테스트 케이스마다 답을 정수 하나로 출력한다.

세 번째 테스트 케이스를 보자. 이 경우 $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$이므로 답은 $6$이다.