PEG Judge - Dog Girls

Halloween Kemonomimi Party 2014

Problem C: Dog Girls

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 S is magic if and only if |S| ≥ 2 and you can rotate it left by at least one but less than |S| positions such that the rotated word forms the original word. More formally, a word S is magic if and only if there exists an index i (0 < i < |S|) such that S_{i + j(mod|S|)} = S_j (0 ≤ j < |S|) (the first letter of S is at index 0).

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 end when she spoke, you will have to settle for finding out how many distinct spells she could have cast.

Input Format

The first and only line will have S, the sequence of letters the dog-girl mumbled (1 ≤ |S| ≤ 5000).
At least 10% of the test cases will have 1 ≤ |S| ≤ 100.
Another 15% of the test cases will have 1 ≤ |S| ≤ 400.
Another 25% of the test cases will have 1 ≤ |S| ≤ 1000.
Another 20% of the test cases will have 1 ≤ |S| ≤ 3000.