The cyclic suffixes
Consider the string S = s_1s_2s_3...s_{n - 1}s_n on alphabet Σ. The cyclic extension of order m of a string S is a string s_1s_2s_3...s_{n - 1}s_ns_1s_2... that consists of m characters. It means that we append the string S to itself until we get the desired length and take the prefix of length m.
The cyclic string Š is an infinite cyclic extension of S.
Consider the suffixes of cyclic string Š. Obviously, there exists no more than |S| different suffixes: the (n+1)-th suffix matches with the first one, the (n+2)-th matches with the second and so on. Moreover, the number of different suffixes can be less than |S|. For example, if S = abab, the first four suffixes of a cyclic string Š are:
Š_1 = ababababab...Š_2 = bababababa...Š_3 = ababababab...Š_4 = bababababa...
There is only two different suffixes, while |S| = 4.
Sort the first |S| suffixes of Š lexicographically. If two suffixes match, put first the suffix with lowest index. Now answer the question: what place does the string Š take in this list?
For example, consider the string S = cabcab:
(1) Š_2 = abcabcabca...(2) Š_5 = abcabcabca...(3) Š_3 = bcabcabcab...(4) Š_6 = bcabcabcab...(5) Š_1 = cabcabcabc...(6) Š_4 = cabcabcabc...
The cyclic string Š_ = Š_1 takes the fifth place.
You are given a string S. Find the position of cyclic string Š_ in the list of suffixes.
Input
One string S (1 ≤ |S| ≤ 1000000), consisting of lowercase Latin letters.
Output
Print the position of the string Š in the list of the first |S| suffixes.