A totem pole is carved with a single row of glyphs, encoded as a string of lowercase English letters. A symmetric run is any subsequence (glyphs chosen left to right, not necessarily adjacent, keeping their order) that reads identically forward and backward.
Find the length of the longest symmetric run that can be selected from the carving.
Input format
A single line containing the glyph string s (lowercase English letters only).
Output format
A single integer: the length of the longest palindromic subsequence of s.
Constraints
- 1 <= length of
s<= 2000 scontains only lowercase English letters (a-z).