Jeśli napis można rozłożyć do postaci $AABB$, gdzie $A$ i $B$ są dowolnymi niepustymi napisami, taki rozkład tego napisu nazywamy doskonałym.

Na przykład dla napisu aabaabaa, przyjmując $A=\mathrm{aab}$ i $B=\mathrm{a}$, otrzymujemy jeden ze sposobów rozłożenia go do postaci $AABB$.

Napis może nie mieć żadnego doskonałego rozkładu lub mieć ich więcej niż jeden. Na przykład przyjmując $A=\mathrm{a}$ i $B=\mathrm{baa}$, również możemy przedstawić powyższy napis w postaci $AABB$. Natomiast napis abaabaa nie ma doskonałego rozkładu.

Dany jest napis $S$ długości $n$. Należy obliczyć łączną liczbę doskonałych rozkładów wśród wszystkich sposobów rozkładu wszystkich jego podnapisów. Podnapis oznacza tutaj spójny fragment napisu.

Należy zwrócić uwagę na następujące kwestie:

1. Takie same podnapisy występujące na różnych pozycjach uznajemy za różne podnapisy; doskonałe rozkłady każdego z nich wliczamy do odpowiedzi.
2. W rozkładzie dopuszcza się $A=B$. Na przykład cccc ma rozkład $A=B=\mathrm{c}$.
3. Sam napis również jest swoim podnapisem.

Wejście

Plikiem wejściowym jest excellent.in.

Każdy plik wejściowy zawiera wiele zestawów danych. Pierwszy wiersz zawiera jedną liczbę całkowitą $T$, oznaczającą liczbę zestawów. Gwarantuje się, że $1\le T\le10$.

Każdy z kolejnych $T$ wierszy zawiera napis $S$ złożony wyłącznie z małych liter alfabetu angielskiego, o znaczeniu podanym w treści zadania.

Wyjście

Plikiem wyjściowym jest excellent.out.

Wypisz $T$ wierszy, każdy z jedną liczbą całkowitą: łączną liczbą doskonałych rozkładów wśród wszystkich rozkładów wszystkich podnapisów napisu $S$.

Przykład

Wejście 1

4
aabbbb
cccccc
aabaabaabaa
bbaabaababaaba

Wyjście 1

3
5
4
7

Uwagi

Przez $S[i,j]$ oznaczamy podnapis napisu $S$ od znaku $i$ do znaku $j$ (numeracja zaczyna się od $1$).

W pierwszym zestawie danych istnieją $3$ podnapisy mające doskonałe rozkłady:

$S[1,4]=\mathrm{aabb}$, z doskonałym rozkładem $A=\mathrm{a}$, $B=\mathrm{b}$;

$S[3,6]=\mathrm{bbbb}$, z doskonałym rozkładem $A=\mathrm{b}$, $B=\mathrm{b}$;

$S[1,6]=\mathrm{aabbbb}$, z doskonałym rozkładem $A=\mathrm{a}$, $B=\mathrm{bb}$.

Pozostałe podnapisy nie mają doskonałych rozkładów, więc odpowiedź dla pierwszego zestawu wynosi $3$.

W drugim zestawie istnieją dwa rodzaje podnapisów mających doskonałe rozkłady, łącznie $4$ takie podnapisy:

Podnapisy $S[1,4]=S[2,5]=S[3,6]=\mathrm{cccc}$ mają ten sam doskonały rozkład: $A=\mathrm{c}$, $B=\mathrm{c}$. Ponieważ jednak występują na różnych pozycjach, trzeba policzyć go $3$ razy.

Podnapis $S[1,6]=\mathrm{cccccc}$ ma $2$ doskonałe rozkłady: $A=\mathrm{c}$, $B=\mathrm{cc}$ oraz $A=\mathrm{cc}$, $B=\mathrm{c}$. Są to różne rozkłady tego samego podnapisu i oba trzeba wliczyć do odpowiedzi.

Odpowiedź dla drugiego zestawu wynosi zatem $3+2=5$.

W trzecim zestawie zarówno $S[1,8]$, jak i $S[4,11]$ mają po $2$ doskonałe rozkłady. Podnapis $S[1,8]$ jest przykładem z treści zadania, więc odpowiedź wynosi $2+2=4$.

W czwartym zestawie podnapisy $S[1,4]$, $S[6,11]$, $S[7,12]$, $S[2,11]$ oraz $S[1,8]$ mają po $1$ doskonałym rozkładzie, a $S[3,14]$ ma $2$ doskonałe rozkłady. Odpowiedź wynosi zatem $5+2=7$.

Przykład 2

Zobacz pliki excellent/excellent2.in i excellent/excellent2.ans w katalogu zawodnika.

Przykład 3

Zobacz pliki excellent/excellent3.in i excellent/excellent3.ans w katalogu zawodnika.

Podzadania

Dla wszystkich testów gwarantuje się $1\le T\le10$. Poniższe ograniczenia dotyczą pojedynczego zestawu danych wejściowych, czyli każdy z $T$ zestawów w danym teście spełnia te ograniczenia.

Przyjmijmy, że $n$ jest długością napisu $S$. Szczegółowe ograniczenia dla każdego testu podano w tabeli: