如果一個字串可以被拆分為 $AABB$ 的形式，其中 $A$ 和 $B$ 是任意非空字串，則我們稱該字串的這種拆分是優秀的。

例如，對於字串 aabaabaa，如果令 $A = \mathtt{aab}$、$B = \mathtt{a}$，我們就找到了這個字串拆分成 $AABB$ 的一種方式。

一個字串可能沒有優秀的拆分，也可能存在不止一種優秀的拆分。比如我們令 $A = \mathtt{a}$、$B = \mathtt{baa}$，也可以用 $AABB$ 表示出上述字串；但是，字串 abaabaa 就沒有優秀的拆分。

現在給出一個長度為 $n$ 的字串 $S$，我們需要求出，在它所有子字串的所有拆分方式中，優秀拆分的總個數。這裡的子字串是指字串中連續的一段。

以下事項需要注意：

1. 出現在不同位置的相同子字串，我們認為是不同的子字串，它們的優秀拆分均會被計入答案。
2. 在一個拆分中，允許出現 $A = B$。例如 cccc 存在拆分 $A = B = \mathtt{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] = \mathtt{aabb}$，優秀的拆分為 $A = \mathtt{a}$、$B = \mathtt{b}$。

$S[3,6] = \mathtt{bbbb}$，優秀的拆分為 $A = \mathtt{b}$、$B = \mathtt{b}$。

$S[1,6] = \mathtt{aabbbb}$，優秀的拆分為 $A = \mathtt{a}$、$B = \mathtt{bb}$。

而剩下的子字串不存在優秀的拆分，所以第一組資料的答案是 3。

第二組資料中，有兩類，總共 4 個子字串存在優秀的拆分：

對於子字串 $S[1,4] = S[2,5] = S[3,6] = \mathtt{cccc}$，它們優秀的拆分相同，均為 $A = \mathtt{c}$、$B = \mathtt{c}$，但由於這些子字串位置不同，因此要計算 3 次。

對於子字串 $S[1,6] = \mathtt{cccccc}$，它優秀的拆分有 2 種：$A = \mathtt{c}$、$B = \mathtt{cc}$ 和 $A = \mathtt{cc}$、$B = \mathtt{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$ 的長度，每個測試點的詳細資料範圍見下表：