Minimum Palindromic Cuts

You are given a string \(s\). Your task is to partition the string into the minimum number of substrings such that each substring is a palindrome. A palindrome is a string that reads the same forwards and backwards. For instance, if \(s = "aab"\), you can split it into \(\{ "aa", "b" \}\) with just one cut, and every substring is a palindrome.

Your program should determine the minimum number of cuts needed to achieve this valid palindromic partitioning.

Note: The input string \(s\) consists of only lowercase English letters.

inputFormat

The input consists of a single line containing the string \(s\). The string is read from standard input.

outputFormat

Output a single integer, which represents the minimum number of cuts needed to partition the string such that every substring is a palindrome. The result should be printed to standard output.

## sample

aab

1

</p>