文字列を $AABB$ という形に分割でき、$A$ と $B$ が任意の空でない文字列であるとき、その文字列のこの分割を優れた分割と呼びます。

例えば、文字列 aabaabaa に対して $A=\texttt{aab},B=\texttt{a}$ とすると、この文字列を $AABB$ に分割する方法の 1 つが得られます。

文字列には優れた分割が存在しないことも、複数存在することもあります。例えば、$A=\texttt{a},B=\texttt{baa}$ としても、上記の文字列を $AABB$ で表せます。一方、文字列 abaabaa には優れた分割がありません。

長さ $n$ の文字列 $S$ が与えられます。そのすべての部分文字列のすべての分割方法に含まれる、優れた分割の総数を求めてください。ここで、部分文字列とは文字列中の連続する一部分を指します。

次の点に注意してください。

1. 異なる位置に現れる同一の部分文字列は、異なる部分文字列と見なします。それぞれの優れた分割を、すべて答えに数えます。
2. 1 つの分割で $A=B$ となってもかまいません。例えば、cccc には $A=B=\texttt{c}$ という分割があります。
3. 文字列そのものも、その部分文字列です。

入力

入力ファイルは excellent.in です。

各入力ファイルには複数のテストケースが含まれます。最初の行には、テストケース数を表す整数 $T$ が 1 つだけ与えられます。$1\le T\le 10$ が保証されます。

続く $T$ 行には、それぞれ英小文字だけからなる文字列 $S$ が 1 つ与えられます。意味は問題文のとおりです。

出力

出力ファイルは excellent.out です。

$T$ 行出力してください。各行には、文字列 $S$ のすべての部分文字列のすべての分割に含まれる、優れた分割の総数を表す整数を 1 つ出力してください。

入出力例

入力 1

4
aabbbb
cccccc
aabaabaabaa
bbaabaababaaba

出力 1

3
5
4
7

注記

$S[i,j]$ は、文字列 $S$ の $i$ 番目から $j$ 番目までの文字からなる部分文字列を表します（$1$ から数えます）。

1 番目のテストケースには、優れた分割を持つ部分文字列が 3 つあります。

$S[1,4]=\texttt{aabb}$ の優れた分割は、$A=\texttt{a},B=\texttt{b}$ です。

$S[3,6]=\texttt{bbbb}$ の優れた分割は、$A=\texttt{b},B=\texttt{b}$ です。

$S[1,6]=\texttt{aabbbb}$ の優れた分割は、$A=\texttt{a},B=\texttt{bb}$ です。

残りの部分文字列には優れた分割がないため、1 番目のテストケースの答えは $3$ です。

2 番目のテストケースには、2 種類、合計 4 つの部分文字列が優れた分割を持ちます。

部分文字列 $S[1,4]=S[2,5]=S[3,6]=\texttt{cccc}$ の優れた分割は同じで、いずれも $A=\texttt{c},B=\texttt{c}$ です。しかし、これらの部分文字列は位置が異なるので、3 回数えます。

部分文字列 $S[1,6]=\texttt{cccccc}$ の優れた分割は、$A=\texttt{c},B=\texttt{cc}$ と $A=\texttt{cc},B=\texttt{c}$ の 2 通りあります。同じ部分文字列の異なる分割なので、両方を答えに数えます。

したがって、2 番目のテストケースの答えは $3+2=5$ です。

3 番目のテストケースでは、$S[1,8]$ と $S[4,11]$ にそれぞれ 2 通りの優れた分割があります。$S[1,8]$ は問題文中の例なので、答えは $2+2=4$ です。

4 番目のテストケースでは、$S[1,4],S[6,11],S[7,12],S[2,11],S[1,8]$ にそれぞれ 1 通り、$S[3,14]$ に 2 通りの優れた分割があるので、答えは $5+2=7$ です。

入出力例 2

選手用ディレクトリ内の excellent/excellent2.in と excellent/excellent2.ans を参照してください。

入出力例 3

選手用ディレクトリ内の excellent/excellent3.in と excellent/excellent3.ans を参照してください。

小課題

すべてのテストケースについて、$1\le T\le 10$ が保証されます。以下の制約は、いずれも 1 つの入力データに対するものです。すなわち、同じテストケース内の $T$ 個のデータは、すべてその制約を満たします。

$n$ を文字列 $S$ の長さとします。各テストケースの詳しいデータ範囲は、次の表のとおりです。