Palindrome Partitioning

Time limit

Memory limit

128 MB

Problem

A given string should be divided into several palindromic substrings. For example, ABACABA can be divided as {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, or {ABACABA}.

Find the minimum number of pieces needed to divide the entire string into palindromic substrings.

Input

The first line contains a string consisting only of uppercase English letters. Its length is at most 2,500.

Output

Print the minimum number of pieces in a palindrome partition of the string.