Vous disposez d'une chaîne $s$ composée de lettres minuscules de l'alphabet anglais.

Considérons un segment $[\ell, r]$ tel que $2 \le \ell \le r \le |s|$. Définissons $f(\ell, r)$ comme la longueur du plus long suffixe de la sous-chaîne $s[1, \ell - 1]$ tel que ce suffixe puisse être décomposé en préfixes de la sous-chaîne $s[\ell, r]$. S'il n'existe aucun suffixe de ce type, alors $f(\ell, r) = 0$.

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

Entrée

La première ligne contient un entier unique $t$ ($1 \le t \le 10^5$) — le nombre de cas de test. La description des cas de test suit.

La seule ligne de chaque cas de test contient la chaîne $s$ ($2 \le |s| \le 2 \cdot 10^5$) composée de lettres minuscules de l'alphabet anglais.

Il est garanti que la somme des $|s|$ pour tous les cas de test n'excède pas $2 \cdot 10^5$.

Sortie

Pour chaque cas de test, affichez un entier unique — la réponse au problème.

Exemples

Entrée 1

8
aa
ab
ababa
abaaba
abacaba
abaaababaab
aababcabcbc
abcdabcabaabcd

Sortie 1

0
0
6
7
0
74
51
20

Remarque

Considérons le troisième cas de test. Dans ce cas, $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$. La réponse est donc 6.