问题描述
Alex非常喜欢做和字符串相关的算法提. 在解决那道计算长度最多为$n$的prefix-square free字符串个数之后, he想要知道对于一个给定的字符串$s$, 有多少连续子串是prefix-suffix-square free的.
一个字符串被称为square当且仅当它可以由两个相同的串连接而成. 例如, "abab", "aa"是square, 而"aaa", "abba"不是. 一个字符串是prefix-suffix-square free的当且仅当他的任何前缀或者后缀都不是square.
输入描述
输入包含多组数据, 第一行包含一个整数$T$表示测试数据组数. 对于每组数据:
第一行包含一个字符串$s=s_{1}s_{2}...s_{n}$ $(1 \le n \le 10^5)$, 仅包含小写字母.
输入最多有$1000$组数据, 并且所有数据中$n$的和不超过$10^6$.
输出描述
对于每组数据, 输出prefix-suffix-square free子串的个数.
输入样例
4
aaaaa
aabcd
aaabbbccc
kurakujoudo
输出样例
5
11
12
66
