eolymp
bolt
Try our new interface for solving problems
Problems

The cyclic suffixes (Easy)

The cyclic suffixes (Easy)

Time limit 1 second
Memory limit 64 MiB

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 strings_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 data

One string S (1 ≤ |S| ≤ 30), consisting of lowercase Latin letters.

Output data

Print the position of the string Š in the list of the first |S| suffixes.

Examples

Input example #1
abracadabra
Output example #1
3