Smallest Palindromic Subsequence Length

Given a string (s), determine the length of the smallest palindromic subsequence that can be obtained by removing zero or more characters from (s).

Note that any single character is a palindrome. Hence, for any non-empty string, the answer is always (1), and for an empty string the answer is (0).

inputFormat

The input consists of a single line containing the string (s).

outputFormat

Output a single integer representing the length of the smallest palindromic subsequence accessible from (s). Formally, the answer is given by: [ \text{answer} = \begin{cases} 1 & \text{if } s \neq "" \ 0 & \text{if } s = "" \end{cases} ]## sample

a

1