Mi Re Do Si La? So Fa!

题号：NC241128
时间限制：C/C++/Rust/Pascal 8秒，其他语言16秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

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

For a string $s$ with length $n$ , $p$ is a period of $n$ if it satisfies $p | n$ and $s_i = s_{i+p}, \forall 0 \leq i < n - p$ .

For a string $s$ , define its beauty $f(s)$ as the sum of its periods.

For example, $aaaa$ has periods $1, 2, 4$ , so it has beauty $f(aaaa) = 7$ , $aba$ has only one period $3$ , so $f(aba) = 3$ .

Now, given a string $s$ consisting of lowercase English letters, you need to calculate $\sum_{0 \leq l \leq r < |s|} f(s_{l,r})$ , i.e., the sum of beauty over all substrings of $s$ .

输入描述:

The first line contains an integer , denoting the number of test cases. .

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

It is guaranteed that the sum of  over all test cases won't exceed .

输出描述:

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

示例1

输入

复制

3
crazythursdaykfcvmefifty
mmrooe
qaqqaq

输出

复制

2600
58
60