小青鱼非常喜欢字符串理论。今天，小青鱼邀请你和他一起研究人类的昵称。

在小青鱼的世界中，人类的昵称都可以表示为仅包含英文小写字母（a 到 z）的字符串。例如，“qingyu”、“xiuga”是人类的昵称，但“Abacde”不是。

小青鱼认为一个名字 $s$ 是 Lyndon 字符串，当且仅当对于 $s$ 的每个真后缀* $t$，$s$ 的字典序都严格小于 $t$。例如，“abacde”是一个 Lyndon 字符串，但“qingyu”不是（因为原字符串的字典序不小于其真后缀“ingyu”）。

现在，小青鱼给你一个人类昵称 $s$，你需要计算有多少对不同的 $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