Palindrome Partitioning

A string partition is called a palindromic partition if every substring in this partition is a palindrome. For example, the string "ababbbabbababa" can be partitioned as "aba|b|bbabb|a|b|aba" — this is an example of a palindromic partition.

Determine the minimum number of cuts required for the palindromic partitioning of a given string. For example:

• for the string "$ababbbabbababa$" a minimum of $3$ cuts are needed to create the partition "$a|babbbab|b|ababa$";

• if the string is already a palindrome, $0$ cuts are needed;

• if all the characters of a string of length $n$ are different, the minimum number of cuts required is $n-1$.

Input

One string $s$ of length no more than $1000$.

Output

Print the minimum number of cuts needed for the palindromic partitioning of the string $s$.

Examples