Se te da una cadena $s$ que consiste en letras minúsculas del alfabeto inglés.

Consideremos un segmento $[\ell, r]$ tal que $2 \le \ell \le r \le |s|$. Definamos $f(\ell, r)$ como la longitud del sufijo más largo de la subcadena $s[1, \ell - 1]$ tal que este sufijo pueda ser dividido en prefijos de la subcadena $s[\ell, r]$. Si no existen tales sufijos, entonces $f(\ell, r) = 0$.

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

Entrada

La primera línea contiene un único entero $t$ ($1 \le t \le 10^5$) — el número de casos de prueba. A continuación sigue la descripción de los casos de prueba.

La única línea de cada caso de prueba contiene la cadena $s$ ($2 \le |s| \le 2 \cdot 10^5$) que consiste en letras minúsculas del alfabeto inglés.

Se garantiza que la suma de $|s|$ para todos los casos de prueba no excede $2 \cdot 10^5$.

Salida

Para cada caso de prueba, imprime un único entero — la respuesta al problema.

Ejemplos

Entrada 1

8
aa
ab
ababa
abaaba
abacaba
abaaababaab
aababcabcbc
abcdabcabaabcd

Salida 1

1
0
6
7
0
74
51
20

Nota

Consideremos el tercer caso de prueba. En este caso, $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$. Por lo tanto, la respuesta es 6.