Lässt sich eine Zeichenkette in der Form $AABB$ zerlegen, wobei $A$ und $B$ beliebige nichtleere Zeichenketten sind, so nennen wir diese Zerlegung ausgezeichnet.

Für die Zeichenkette aabaabaa finden wir beispielsweise mit $A=\texttt{aab}$ und $B=\texttt{a}$ eine Darstellung in der Form $AABB$.

Eine Zeichenkette kann keine oder auch mehrere ausgezeichnete Zerlegungen besitzen. Mit $A=\texttt{a}$ und $B=\texttt{baa}$ lässt sich die obige Zeichenkette ebenfalls als $AABB$ darstellen. Dagegen besitzt die Zeichenkette abaabaa keine ausgezeichnete Zerlegung.

Gegeben ist nun eine Zeichenkette $S$ der Länge $n$. Gesucht ist die Gesamtzahl ausgezeichneter Zerlegungen unter allen Zerlegungen aller ihrer Teilzeichenketten. Eine Teilzeichenkette ist hier ein zusammenhängender Abschnitt einer Zeichenkette.

Beachte Folgendes:

1. Gleiche Teilzeichenketten an unterschiedlichen Positionen gelten als verschiedene Teilzeichenketten. Ihre ausgezeichneten Zerlegungen werden jeweils zur Antwort gezählt.
2. In einer Zerlegung ist $A=B$ erlaubt. Beispielsweise besitzt cccc die Zerlegung $A=B=\texttt{c}$.
3. Die Zeichenkette selbst ist ebenfalls eine ihrer Teilzeichenketten.

Eingabe

Die Eingabedatei heißt excellent.in.

Jede Eingabedatei enthält mehrere Testfälle. Ihre erste Zeile enthält nur eine ganze Zahl $T$, die Anzahl der Testfälle. Es gilt $1\le T\le10$.

Die folgenden $T$ Zeilen enthalten jeweils eine Zeichenkette $S$, die nur aus englischen Kleinbuchstaben besteht und die oben beschriebene Bedeutung hat.

Ausgabe

Die Ausgabedatei heißt excellent.out.

Gib $T$ Zeilen mit jeweils einer ganzen Zahl aus: die Gesamtzahl ausgezeichneter Zerlegungen unter allen Zerlegungen aller Teilzeichenketten von $S$.

Beispiele

Eingabe 1

4
aabbbb
cccccc
aabaabaabaa
bbaabaababaaba

Ausgabe 1

3
5
4
7

Hinweis

Mit $S[i,j]$ bezeichnen wir die Teilzeichenkette vom $i$-ten bis zum $j$-ten Zeichen von $S$ (die Zählung beginnt bei $1$).

Im ersten Testfall besitzen insgesamt $3$ Teilzeichenketten eine ausgezeichnete Zerlegung:

$S[1,4]=\texttt{aabb}$ mit der ausgezeichneten Zerlegung $A=\texttt{a}$, $B=\texttt{b}$;

$S[3,6]=\texttt{bbbb}$ mit der ausgezeichneten Zerlegung $A=\texttt{b}$, $B=\texttt{b}$;

$S[1,6]=\texttt{aabbbb}$ mit der ausgezeichneten Zerlegung $A=\texttt{a}$, $B=\texttt{bb}$.

Die übrigen Teilzeichenketten besitzen keine ausgezeichnete Zerlegung, daher lautet die Antwort im ersten Testfall $3$.

Im zweiten Testfall besitzen insgesamt $4$ Teilzeichenketten aus zwei Kategorien ausgezeichnete Zerlegungen:

Die Teilzeichenketten $S[1,4]=S[2,5]=S[3,6]=\texttt{cccc}$ besitzen alle dieselbe ausgezeichnete Zerlegung $A=\texttt{c}$, $B=\texttt{c}$. Da sie jedoch an verschiedenen Positionen liegen, wird diese dreimal gezählt.

Die Teilzeichenkette $S[1,6]=\texttt{cccccc}$ besitzt zwei ausgezeichnete Zerlegungen: $A=\texttt{c}$, $B=\texttt{cc}$ und $A=\texttt{cc}$, $B=\texttt{c}$. Diese verschiedenen Zerlegungen derselben Teilzeichenkette werden beide zur Antwort gezählt.

Daher lautet die Antwort im zweiten Testfall $3+2=5$.

Im dritten Testfall besitzen $S[1,8]$ und $S[4,11]$ jeweils zwei ausgezeichnete Zerlegungen. Dabei ist $S[1,8]$ das Beispiel aus der Aufgabenstellung. Daher lautet die Antwort $2+2=4$.

Im vierten Testfall besitzen $S[1,4]$, $S[6,11]$, $S[7,12]$, $S[2,11]$ und $S[1,8]$ jeweils eine ausgezeichnete Zerlegung; $S[3,14]$ besitzt zwei. Daher lautet die Antwort $5+2=7$.

Beispiel 2

Siehe excellent/excellent2.in und excellent/excellent2.ans im Teilnehmerverzeichnis.

Beispiel 3

Siehe excellent/excellent3.in und excellent/excellent3.ans im Teilnehmerverzeichnis.

Teilaufgaben

Für alle Testpunkte gilt $1\le T\le10$. Die folgenden Einschränkungen beziehen sich jeweils auf einen einzelnen Testfall. Das heißt, alle $T$ Testfälle desselben Testpunkts erfüllen diese Einschränkungen.

Sei $n$ die Länge der Zeichenkette $S$. Die genauen Datenbereiche jedes Testpunkts stehen in der folgenden Tabelle: