This morning, you woke up and realized that some dogs have turned into girls! In light of this exciting event, you immediately put on your wizard robes and walk outside, as everybody knows that dog-girls are magic users. Sure enough, one such sorceress is casting a spell on the street, and struck by awe, you gaze at her intently (so you can see what spell she's casting, of course).
For a dog-girl to use cast a spell, she must speak a magic word (which uniquely corresponds to that spell). A word is magic if and only if and you can rotate it left by at least one but less than positions such that the rotated word forms the original word. More formally, a word is magic if and only if there exists an index such that (the first letter of is at index ).
You hear the sorceress dog-girl mumble a long sequence of lowercase English letters, and you wonder what spell(s) she cast just now. Because you could not discern where the words began and ended when she spoke, you will have to settle for finding out how many distinct spells she could have cast.
The first and only line will have , the sequence of letters the dog-girl mumbled .
At least 10% of the test cases will have .
Another 15% of the test cases will have .
Another 25% of the test cases will have .
Another 20% of the test cases will have .
The first and only line of output should contain the number of distinct substrings of that are magic words.
Sample Input 1
Sample Output 1
Explanation for Sample Output 1
The whole string is a magic word:
abracadabracad. Additionally, no proper substring of
abracadabracad is a magic word.
Sample Input 2
Sample Output 2
Explanation for Sample Output 2
cc are magic words.