Minimum Cuts for Palindrome Partitioning

Given a string s, your task is to determine the minimum number of cuts needed to partition the string such that every substring in the partition is a palindrome. A palindrome is a string that reads the same forwards and backwards, i.e. a string s is a palindrome if \(s = s^R\), where \(s^R\) denotes the reverse of s.

For example, if s = "noonabbad", one optimal way to partition it is "noon | abba | d", which requires 2 cuts.

You are required to read the input from standard input (stdin) and write the result to standard output (stdout).

inputFormat

The input consists of a single line containing a non-empty string s which consists of lowercase letters.

Example:

noonabbad

outputFormat

Output a single integer representing the minimum number of cuts required to partition s such that every substring is a palindrome.

Example:

2

## sample

noonabbad

2