Minimum Palindromic Substrings After a Single Reversal

You are given a string s consisting of lowercase alphabetical characters. You are allowed to perform exactly one substring reversal operation on s. The goal is to obtain the minimum possible number of palindromic substrings by optimally applying the reversal.

A palindrome is a string that reads the same backward as forward. Formally, a string s is a palindrome if it satisfies the condition:

\( s = s^R \)

where \( s^R \) denotes the reverse of \( s \). Note that an empty string is considered a palindrome.

Task: Determine and output the minimum number of palindromic substrings that can be obtained after applying exactly one substring reversal on the given string. It turns out that if the original string is already a palindrome, no reversal is necessary and the answer is 1; otherwise, the best outcome is 2.

Examples:

• For s = "abcddcba", the answer is 1 because s is already a palindrome.
• For s = "madam", the answer is 1.
• For s = "abc", the answer is 2.
• For s = "abaxyz", the answer is 2.
• For an empty string s = "", the answer is 1.

inputFormat

The input consists of a single line containing the string s which may be empty. The string is composed of lowercase alphabetical characters.

Note: The input is to be read from standard input (stdin).

outputFormat

Output a single integer — the minimum number of palindromic substrings that can be obtained after performing exactly one substring reversal on the input string.

Note: The output should be printed to standard output (stdout).

## sample

abcddcba

1