Palindrome Partition

A palindrome is a word that reads the same from left to right and from right to left. Words such as aba and a are palindromes, while abaccbcb and anavolimilana are not.

A word that is not itself a palindrome can be split into several palindromic substrings. Given a word, split it so that every piece is a palindrome and the number of pieces is as small as possible.

For instance, abaccbcb can be split into aba, cc, and bcb, so the answer is 3. It cannot be split into only two palindromic pieces. Likewise, anavolimilana can be split into ana, v, o, limil, and ana, so the answer is 5.

Write a program that prints the minimum number of palindromic substrings needed to partition the given word. If the whole word is already a palindrome, it does not need to be split.

The first line contains one word. The word consists only of lowercase English letters, and its length is at most 2,000.

Print the minimum number of palindromic substrings into which the given word can be split.