Longest Palindromic Subsequence

You are given a string s. Your task is to identify the longest palindromic subsequence in s and output its length.

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 backward as forward.

You can formulate the dynamic programming relation as follows:

\( \text{if } s[i] = s[j] \text{ then } dp[i][j] = dp[i+1][j-1] + 2 \), otherwise \( dp[i][j] = \max(dp[i+1][j], dp[i][j-1]) \). Each single character is considered as a palindrome of length 1.

The input is provided via stdin and the output should be printed to stdout.

inputFormat

The only line of input contains a string s (with no spaces) whose longest palindromic subsequence length is to be determined.

outputFormat

Output a single integer which is the length of the longest palindromic subsequence in the given string.

## sample

bbbab

4

</p>