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