Longest Palindromic Subsequence

Given a string s, your task is to compute the length of its longest palindromic subsequence. A subsequence is a sequence that can be derived from the string by deleting some characters without changing the order of the remaining characters. A palindrome is a string that reads the same forwards and backwards.

The solution can be derived using dynamic programming. Define a 2D array dp such that dp[i][j] represents the length of the longest palindromic subsequence in the substring s[i...j]. The recurrence relation is given by:

$\displaystyle dp[i][j] = \begin{cases} 1 & \text{if } i = j,\\ 2 & \text{if } s[i]=s[j] \text{ and } j = i+1,\\ dp[i+1][j-1]+2 & \text{if } s[i]=s[j],\\ \max(dp[i+1][j],\;dp[i][j-1]) & \text{otherwise.} \end{cases}$

Your program should read the input from stdin and output the result to stdout.

inputFormat

The input consists of a single line containing the string s (with length at least 1). The string can contain only lowercase English letters.

outputFormat

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

## sample

abacaba

7

</p>