Minimum Palindromic Substrings Partitioning

You are given a string s consisting of lowercase English letters. Your task is to partition the string into the minimum number of substrings such that each substring is a palindrome. A palindrome is a string that reads the same from left to right as it does from right to left.

For example, consider the string abacc. One optimal partition is aba and cc, so the answer is 2.

Formally, given a string \( s \) of length \( n \), find the minimum number \( k \) such that there exists a partition of \( s \) into \( k \) palindromic substrings.

Input Constraints: The string s consists solely of lowercase English letters.

inputFormat

The input is given as a single line containing the string s.

outputFormat

Output a single integer representing the minimum number of palindromic substrings into which the string s can be partitioned.

## sample

abacc

2

</p>