#P17966. Call You With Your Name 2
Call You With Your Name 2
Call You With Your Name 2
对于非空字符串 ,如果 的字典序严格小于它的每个非空真后缀,则称 为 Lyndon 串。
真后缀不能等于原串。例如,qqoj 的非空真后缀为 qoj、oj、j。长度为 的字符串没有非空真后缀,因此也是 Lyndon 串。
给定仅包含小写英文字母的字符串 ,求有多少对下标 ,满足 ,且子串 是 Lyndon 串。不同下标区间分别计数,即使它们的内容相同。
输入格式
第一行是测试用例数 。接下来每组数据一行字符串 。
,所有测试用例的字符串长度之和不超过 。
输出格式
每组数据输出一行一个整数,表示合法下标区间的数量。
样例输入
6
aaa
qingyu
littlecyanfish
abacde
abcdefghbidajkad
abcdeabdfag
样例输出
3
9
27
16
58
32