String Strange Sum

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

Consider a segment $[\ell, r]$ such that $2 \leq \ell \leq r \leq |s|$. Let $f(\ell, r)$ be the length of the longest suffix of $s[1, \ell-1]$ that can be divided into prefixes of $s[\ell, r]$. If there is no such suffix, then $f(\ell, r) = 0$.

Find the value of

$\sum_{\ell=2}^{|s|} \sum_{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. Each of the next $t$ lines contains a string $s$ ($2 \leq |s| \leq 2 \cdot 10^5$) made of lowercase English letters. The sum of $|s|$ over all test cases does not exceed $2 \cdot 10^5$.

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

Consider the third test case. Here $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$, and $f(5, 5) = 0$. The answer is $6$.