A decorative mosaic frieze is encoded as a string of lowercase letters. A restoration wants to keep the largest symmetric pattern possible by removing some tiles: find the length of the longest subsequence of the string that is a palindrome (reads the same left to right and right to left).
Input format
Line 1: the frieze string s.
Output format
A single integer: the length of the longest palindromic subsequence of s.
Constraints
- 1 <= length of
s<= 40 sconsists of lowercase English letters only.