During a Data Structures and Algorithms class, Tang was given a string ~S~ consisting entirely of lowercase English letters. Tang wants to split ~S~ into as many contiguous substrings as possible. After splitting, he will rearrange and concatenate all these substrings such that the resulting string is lexicographically smallest.

However, Tang has a special requirement: the final concatenated string must be exactly identical to the original string ~S~.

Help Tang find the maximum number of substrings ~S~ can be split into while satisfying this condition!

Input

• The first and only line contains the string ~S~ ~(1 \le |S| \le 50)~ consisting of lowercase English letters.

Output

• Print a single integer representing the maximum number of parts the string can be split into.

Sample Input 1

aba

Sample Output 1

2

Sample Input 2

babbaba

Sample Output 2

2

Sample Input 3

zzzzz

Sample Output 3

5

Explanation

• For the string aba, we can split it into ~2~ parts: "a" and "ba". Concatenating them to form the lexicographically smallest string yields "aba" (matching the original). If we split it into ~3~ parts "a", "b", and "a", the lexicographically smallest arrangement produces "aab" (which does not match the original).
• For the string babbaba, we can split it into ~2~ parts: "ba" and "bbaba".