Longest Palindromic Subsequence

Given a string S, your task is to compute the length of the longest palindromic subsequence in S. A subsequence is a sequence that can be derived from the string by deleting some or no characters without changing the order of the remaining characters. A palindromic subsequence is a subsequence which reads the same backwards as forwards.

Your solution should work efficiently even for larger strings.

Note: The subsequence does not need to be contiguous. For example, in the string "bbabcbcab", one of the longest palindromic subsequences is "babcbab", which has a length of 7.

inputFormat

The input consists of a single line containing the string S. The string may be empty.

outputFormat

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

## sample

bbabcbcab

7

</p>