Minimum Palindrome Partitioning

You are given a string S consisting of lowercase English letters. Your task is to determine the minimum number of palindromic substrings into which S can be partitioned.

A palindrome is a string that reads the same forwards and backwards. Formally, for a string \(S\) of length \(n\), find the minimum \(k\) such that there exists a partition of \(S = P_1P_2\ldots P_k\) where each \(P_i\) is a palindrome.

Examples:

• For \(S = \texttt{ababa}\), the answer is 1 because the whole string is a palindrome.
• For \(S = \texttt{abc}\), the answer is 3 since no larger palindromic substrings exist other than each single character.
• For \(S = \texttt{aab}\), the answer is 2, which can be partitioned as "aa" and "b".

Implement an efficient algorithm to compute this minimum partition count.

inputFormat

The input consists of a single line containing the string S (1 ≤ |S| ≤ 10⁴), consisting only of lowercase English letters.

outputFormat

Output a single integer — the minimum number of palindromic substrings that the string S can be partitioned into.

## sample

ababa

1

</p>