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 100000.
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".
