A subsequence is formed by deleting zero or more characters without reordering the rest. A string is a palindrome if it reads the same left-to-right and right-to-left. Given a string s, find the length of its longest palindromic subsequence.
Input format
A single line: the string s of lowercase letters a-z.
Output format
A single integer: the length of the longest palindromic subsequence.
Constraints
- 1 <= length of
s<= 1000