Longest Palindromic Subsequence

Given a string \(s\), your task is to determine the length of the longest palindromic subsequence in \(s\). A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

A palindrome is a string that reads the same forward and backward. The subsequence does not have to be contiguous, but the order of the characters must remain the same.

Example: For the string "bbbab", one of the longest palindromic subsequences is "bbbb", so the output is 4.

Note: The input string consists of lowercase English letters only and its length is at least 1.

inputFormat

Input is given via standard input. The first and only line of input contains a non-empty string (s) consisting of lowercase English letters.

outputFormat

Output the length of the longest palindromic subsequence in (s) to standard output.## sample

bbbab

4