小青魚非常喜歡字串理論。今天，小青魚邀請你和他一起研究人類的暱稱。

在小青魚的世界中，人類的暱稱都可以表示為僅包含英文小寫字母（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