Minimum Palindrome Substring Partition

Given a string s, partition it into the minimum number of contiguous substrings such that each substring is a palindrome.

In this problem, the rule is defined as follows:

• If s is an empty string, the answer is 0.
• If s is a palindrome (i.e. \(s = s^{rev}\)), then the answer is 1.
• Otherwise, the answer is defined as the length of s (i.e. each character is considered as an individual palindrome), so the answer is \(|s|\).

Note: Although the term "minimum" is used, for this problem the intended solution follows the simple rule described above.

inputFormat

The input consists of a single line containing a string s. The string can be empty. There are no extra spaces or characters.

Examples:

• 1221
• abc

outputFormat

Output a single integer representing the minimum number of contiguous substrings such that each substring is a palindrome, according to the rules:

1. If the string is empty, print 0.
2. If the string is a palindrome (\(s = s^{rev}\)), print 1.
3. Otherwise print the length of the string, i.e. \(|s|\).

## sample

1221

1