Consider a string \mathbf{S} = s_1s_2s_3\dots s_n over an alphabet , where |\mathbf{S}| = n.
A cyclic extension of order of the string is a string of characters, given by s_1s_2s_3\dots s_ns_1s_2\dots, that is, we concatenate copies of to itself until reaching length , and then take the prefix of length .
The cyclic string \mathbf{\breve{S}} is the infinite cyclic extension of .
Consider the suffixes of the cyclic string \mathbf{\breve{S}}. Obviously, there are at most different suffixes: the (n+1)-th suffix coincides with the first one, the (n+2)-th coincides with the second one, and so on. Moreover, the number of distinct suffixes can be less than . For example, if \mathbf{S} = abab, the first four suffixes of the cyclic string \mathbf{\breve{S}} are:
Here, there are only two distinct suffixes, while n = 4.
Sort the first suffixes of \mathbf{\breve{S}} lexicographically. If two suffixes are identical, the one with the lower index comes first. Now, answer the following question: in what position does the string \mathbf{\breve{S}} itself (i.e., \mathbf{\breve{S}}_1) appear in this ordering?
For example, consider the string \mathbf{S} = cabcab:
Here, the cyclic string \mathbf{\breve{S}} = \mathbf{\breve{S}}_1 takes the fifth place in the list.
You are given a string . Find the position of the cyclic string \mathbf{\breve{S}} among the sorted first suffixes.
The input contains a single string (1 \leq |\mathbf{S}| \leq 30), consisting of lowercase Latin letters.
Print the position of \mathbf{\breve{S}} in the lexicographically sorted list of the first suffixes.
1-nji mysal