A ceramic border is a string s of lowercase English letters, one letter per tile. You want to slice the border into contiguous pieces so that every piece reads the same forward and backward (a palindrome). A slice is a single cut between two adjacent tiles.
Determine the minimum number of cuts needed so that each resulting piece is a palindrome. A string that is already a palindrome needs 0 cuts.
Input format
A single line containing the string s (lowercase English letters only).
Output format
A single integer: the minimum number of cuts.
Constraints
- 1 <= length of
s<= 2000 scontains only lowercase English letters (a-z).