You are given a string s. You want to cut it into contiguous pieces so that every piece is a palindrome. Find the minimum number of cuts required. A string that is already a palindrome needs zero cuts; cutting into p pieces uses p - 1 cuts.
Input format
A single line: a non-empty string s of lowercase letters a-z.
Output format
A single integer: the minimum number of cuts.
Constraints
- 1 <= length of
s<= 2000