Longest Palindromic Subsequence

In this problem, you are given one or more strings, and your task is to compute the length of the longest palindromic subsequence for each string. 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. The answer for each string is denoted by (L = dp[0][n-1]), where (dp[i][j]) is obtained using the recurrence: [ \text{dp}[i][j] = \begin{cases} 1 & \text{if } i == j,\ \text{dp}[i+1][j-1] + 2 & \text{if } s[i] = s[j],\ \max(\text{dp}[i+1][j],\ \text{dp}[i][j-1]) & \text{if } s[i] \neq s[j]. \end{cases} ] The input terminates with a line containing a single asterisk (*) which should not be processed. Your solution must read from standard input and write to standard output.

inputFormat

The input consists of multiple lines. Each line (except the last one) contains a non-empty string (s). The input terminates when a line containing a single asterisk (*) is encountered. You are required to process every string before the termination line.

outputFormat

For each input string (except the termination marker), output one integer on a separate line representing the length of its longest palindromic subsequence.## sample

bbbab
abcde
racecar
a
abcdefedcba
*

4
1
7
1
11