如果一個字串可以拆成 $AABB$ 嘅形式，其中 $A$ 同 $B$ 係任意非空字串，我哋就稱呢個字串嘅呢種拆分係優秀嘅。

例如，對於字串 aabaabaa，如果令 $A=\texttt{aab}$，$B=\texttt{a}$，我哋就搵到呢個字串拆成 $AABB$ 嘅一種方法。

一個字串可能冇優秀嘅拆分，亦可能有多過一種優秀嘅拆分。例如令 $A=\texttt{a}$，$B=\texttt{baa}$，亦可以用 $AABB$ 表示上面個字串；但字串 abaabaa 就冇優秀嘅拆分。

而家畀你一個長度係 $n$ 嘅字串 $S$，我哋要求出，喺佢所有子字串嘅所有拆分方法入面，優秀拆分嘅總數。呢度嘅子字串係指字串入面連續嘅一段。

有以下幾點要注意：

1. 喺唔同位置出現嘅相同子字串，我哋視為唔同嘅子字串，佢哋嘅優秀拆分都會計入答案。
2. 同一個拆分入面，容許 $A=B$。例如 cccc 有拆分 $A=B=\texttt{c}$。
3. 字串本身亦係佢嘅一個子字串。

輸入格式

輸入檔案係 excellent.in。

每個輸入檔案包含多組數據。輸入檔案第一行只有一個整數 $T$，表示數據組數。保證 $1\le T\le 10$。

之後 $T$ 行，每行包含一個只由英文小寫字母組成嘅字串 $S$，意思如題目所述。

輸出格式

輸出檔案係 excellent.out。

輸出 $T$ 行，每行包含一個整數，表示字串 $S$ 所有子字串嘅所有拆分入面，一共有幾多個係優秀嘅拆分。

樣例

輸入格式 1

4
aabbbb
cccccc
aabaabaabaa
bbaabaababaaba

輸出格式 1

3
5
4
7

說明

我哋用 $S[i,j]$ 表示字串 $S$ 第 $i$ 個字元至第 $j$ 個字元嘅子字串（由 $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}$。

其餘子字串冇優秀嘅拆分，所以第一組數據嘅答案係 $3$。

第二組數據入面，有兩類，一共 $4$ 個子字串有優秀嘅拆分：

對於子字串 $S[1,4]=S[2,5]=S[3,6]=\texttt{cccc}$，佢哋嘅優秀拆分相同，都係 $A=\texttt{c}$，$B=\texttt{c}$，但因為呢啲子字串位置唔同，所以要計 $3$ 次；

對於子字串 $S[1,6]=\texttt{cccccc}$，佢有 $2$ 種優秀拆分：$A=\texttt{c}$，$B=\texttt{cc}$，同埋 $A=\texttt{cc}$，$B=\texttt{c}$。佢哋係相同子字串嘅唔同拆分，亦都要計入答案。

所以第二組數據嘅答案係 $3+2=5$。

第三組數據入面，$S[1,8]$ 同 $S[4,11]$ 各自有 $2$ 種優秀拆分，其中 $S[1,8]$ 就係問題描述入面嘅例子，所以答案係 $2+2=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$。以下嘅數據限制都係針對單組輸入數據，即係同一個測試點入面嘅 $T$ 組數據，都符合限制條件。

我哋設 $n$ 為字串 $S$ 嘅長度，每個測試點嘅詳細數據範圍見下表：