Dany jest ciąg znaków $s$ składający się z małych liter alfabetu angielskiego.

Rozważmy przedział $[\ell, r]$ taki, że $2 \le \ell \le r \le |s|$. Zdefiniujmy $f(\ell, r)$ jako długość najdłuższego przyrostka podciągu $s[1, \ell - 1]$, który można podzielić na prefiksy podciągu $s[\ell, r]$. Jeśli taki przyrostek nie istnieje, to $f(\ell, r) = 0$.

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

Wejście

Pierwsza linia zawiera jedną liczbę całkowitą $t$ ($1 \le t \le 10^5$) — liczbę zestawów danych. Następnie opisano zestawy danych.

Jedyna linia każdego zestawu danych zawiera ciąg znaków $s$ ($2 \le |s| \le 2 \cdot 10^5$) składający się z małych liter alfabetu angielskiego.

Gwarantuje się, że suma długości $|s|$ dla wszystkich zestawów danych nie przekracza $2 \cdot 10^5$.

Wyjście

Dla każdego zestawu danych wypisz jedną liczbę całkowitą — odpowiedź na zadany problem.

Przykład

Wejście 1

8
aa
ab
ababa
abaaba
abacaba
abaaababaab
aababcabcbc
abcdabcabaabcd

Wyjście 1

0
1
6
7
0
74
51
20

Uwagi

Rozważmy trzeci zestaw danych. W tym przypadku $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$. Zatem odpowiedź wynosi $6$.