Minimum Palindromic Cuts

Given a string (s) consisting of lowercase English letters, determine the minimum number of cuts needed to partition (s) into substrings, each of which is a palindrome. A palindrome is a string that reads the same forwards and backwards (for example, (racecar) is a palindrome). Formally, if the string is partitioned into (k) palindromic substrings, the minimum number of cuts required is (k - 1). Your task is to compute this value optimally.

Example:
For (s = \texttt{aab}), one optimal partition is (\texttt{aa|b}) where only 1 cut is required, so the answer is 1.

inputFormat

The input consists of a single line containing the string (s). The string will contain only lowercase English letters and no spaces.

outputFormat

Output a single integer representing the minimum number of cuts required so that every substring is a palindrome.## sample

a

0