Repeating

Time Limit: 20000/10000 MS (Java/Others)

Memory Limit: 131072/131072 K (Java/Others)

Description

Cloud gets a string which contains only lower-case letters from Miceren as a birthday gift.

Since Cloud hates repeating, if a substring can be divided into several equal strings, she will be very disgusted. For example, "abcabcabc" is very disgusting for her, but "abca" is just ok.

Now, Cloud wants to know how many non-empty substring would not disgust her. As you know, Miceren is not good at counting, can you help him?

Input

The first line contains a single integer $T$, indicating the number of test cases.

Each test case contains only one line, containing the string.

$T$ is about 10.

The length of string will not exceed 100100.

Output

For each test case, print the answer.

Sample Input

1 abcabc

Sample Output

20
Hint
The only substring which disgusts Cloud is the whole string "abcabc".

Hint

hujie

Source

赛码"BestCoder"杯中国大学生程序设计冠军赛

提交代码