Consider the string \textbf{S = s_1s_2s_3 \ldots s_{n-1}s_n} over the alphabet . The cyclic extension of order of the string is a string s_1s_2s_3 \ldots s_{n-1}s_ns_1s_2 \ldots of length . This means we append the string to itself until we reach the required length, and then take a prefix of length .
The cyclic string \textbf{Š} is the infinite cyclic extension of .
Consider the suffixes of the cyclic string \textbf{Š}. Clearly, there are at most different suffixes: the (n+1)-th suffix matches the first, the (n+2)-th matches the second, and so on. In fact, there can be even fewer distinct suffixes. For example, if \textbf{S} = abab, then the first four suffixes of the cyclic string \textbf{Š} are:
\textbf{Š}_1 = ababababab \ldots
\textbf{Š}_2 = bababababa \ldots
\textbf{Š}_3 = ababababab \ldots
\textbf{Š}_4 = bababababa \ldots
There are only two different suffixes, while |\textbf{S}| = 4.
Sort the first suffixes of \textbf{Š} lexicographically. If two suffixes match, place the one with the lower index first. The question is: what is the position of the string \textbf{Š} itself in this list?
For example, for the string \textbf{S} = cabcab:
(1) \textbf{Š}_2 = abcabcabca \ldots
(2) \textbf{Š}_5 = abcabcabca \ldots
(3) \textbf{Š}_3 = bcabcabcab \ldots
(4) \textbf{Š}_6 = bcabcabcab \ldots
(5) \textbf{Š}_1 = cabcabcabc \ldots
(6) \textbf{Š}_4 = cabcabcabc \ldots
Here, the cyclic string \textbf{Š} = \textbf{Š}_1 takes the fifth place.
You are given a string . Find the position of the cyclic string \textbf{Š} in this list.
The input file contains a single string (1 \leq |S| \leq 1000000), consisting of uppercase Latin letters.
Print a single number — the position of the string \textbf{Š} among the first suffixes in the described order.
Example 1