P8605 - Mi Re Do Si La? So Fa!

内存限制：256 MB 时间限制：8 S 标准输入输出

题目类型：传统评测方式：文本比较上传者：

提交：1 通过：1

XiYue likes watching the white moon. Under the moonlight, each star has its own beauty. The same thing holds for strings.

For a string

with length

n

is a period of

n

if it satisfies

and

.

For a string

, define its beauty

as the sum of its periods.

For example,

a

has periods

, so it has beauty

has only one period

, so

Now, given a string

consisting of lowercase English letters, you need to calculate

, i.e., the sum of beauty over all substrings of

The first line contains an integer

T

, denoting the number of test cases.

.
For each test case, the first line contains a string consisting of lowercase English letters, denoting

s

.
It is guaranteed that the sum of

over all test cases won't exceed

^{6}

For each test case, output an integer in a single line, denoting the answer.

3
crazythursdaykfcvmefifty
mmrooe
qaqqaq

2600
58
60

8605: Mi Re Do Si La? So Fa!