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?
输入解释
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.
输出解释
For each test case, print the answer.
输入样例
1
abcabc
输出样例
20
提示
The only substring which disgusts Cloud is the whole string "abcabc".