Given a string S[1..n] . A rotation on S is that we move the first character to the right-most of the string. More specific, after a rotation, S becomes T = S[2..n] + S[1].

For example: S = abcaa, then after a rotation we have S = bcaaa.

Find the minimum number of rotations to make S become the smallest lexicographical order string.

Input

A single line contains a string S. S contains only small letters of English alphabet (‘a’ .. ‘z’), and the length of S is not more than 100000.

Output

A single line contains an integer which represents the minimum number of rotations.

Example

Input:
mississippi
Output:
10

Test cases and time limit have been updated. Some accepted solution got TLE.