Minimum Palindrome Partitioning

Given a string S, your task is to compute the minimum number of cuts needed to partition the string into substrings, where each substring is a palindrome.

A palindrome is a string that reads the same forwards and backwards. Formally, let S be the input string and c(S) be the minimum number of cuts required so that every substring is a palindrome. If the entire string is already a palindrome, then c(S) = 0. Otherwise, c(S) can be computed by considering all possible partitions.

For example, for S = "aab", the answer is 1, since the substring partition "aa" and "b" meets the requirements.

Note: In this problem, you need to read from standard input and output the result to standard output.

inputFormat

The input consists of a single line containing the string S (1 ≤ |S| ≤ 1000) composed of lowercase letters.

outputFormat

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

aab

1