小青魚非常鍾意字符串理論。今日，小青魚邀請你同佢一齊研究人類嘅暱稱。

喺小青魚嘅世界入面，人類嘅暱稱都可以表示為僅包含英文細楷字母（a 到 z）嘅字符串。例如，"qingyu"、"xiuga" 係人類嘅暱稱，但 "Abacde" 唔係。

小青魚認為一個名字 $s$ 係 Lyndon 字符串，當且僅當對於 $s$ 嘅每個真後綴* $t$，$s$ 嘅字典序都嚴格細過 $t$。例如，"abacde" 係一個 Lyndon 字符串，但 "qingyu" 唔係（因為原字符串嘅字典序唔細過佢嘅真後綴 "ingyu"）。

而家，小青魚畀你一個人類暱稱 $s$，你需要計算有幾多對唔同嘅 $(l, r)$ 滿足 $1 \le l \le r \le |s|$ 且 $s[l \dots r]$ 係 Lyndon 字符串。

* 真後綴係指非空且唔等於原字符串嘅後綴。例如，"qqoj" 有 $3$ 個真後綴，分別係 "j"、"oj" 同 "qoj"。

輸入格式

輸入包含多組測試數據。第一行包含一個整數 $T$ ($1 \le T$)，表示測試用例嘅數量。

對於每個測試用例，輸入包含一行，為一個字符串 $s$ ($1 \le |s| \le 2 \times 10^5$)，表示人類嘅暱稱。

保證所有測試用例入面 $|s|$ 嘅總和唔超過 $2 \times 10^5$。

輸出格式

對於每個測試用例，輸出一行，包含一個整數，表示答案。

樣例

輸入樣例 1

6
aaa
qingyu
littlecyanfish
abacde
abcdefghbidajkad
abcdeabdfag

輸出樣例 1

3
9
27
16
58
32