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.