#P17966. Call You With Your Name 2

Call You With Your Name 2

Call You With Your Name 2

对于非空字符串 ss,如果 ss 的字典序严格小于它的每个非空真后缀,则称 ss 为 Lyndon 串。

真后缀不能等于原串。例如,qqoj 的非空真后缀为 qoj、oj、j。长度为 11 的字符串没有非空真后缀,因此也是 Lyndon 串。

给定仅包含小写英文字母的字符串 ss,求有多少对下标 (l,r)(l,r),满足 1≤l≤r≤∣s∣1\le l\le r\le|s|,且子串 s[l…r]s[l\ldots r] 是 Lyndon 串。不同下标区间分别计数,即使它们的内容相同。

输入格式

第一行是测试用例数 T≥1T\ge1。接下来每组数据一行字符串 ss。

1≤∣s∣≤2×1051\le|s|\le2\times10^5,所有测试用例的字符串长度之和不超过 2×1052\times10^5。

输出格式

每组数据输出一行一个整数,表示合法下标区间的数量。

样例输入

6
aaa
qingyu
littlecyanfish
abacde
abcdefghbidajkad
abcdeabdfag

样例输出

3
9
27
16
58
32