测试数据来自 system/3061

时间限制：1秒　　内存限制：256M

---

【问题描述】

　　从一个字符串中取出若干个字符，然后把这些字符按照其在字符串中出现的顺序依次连接起来得到一个新的字符串，这个新字符串称为 子序列串。

　　如果一个字符串从左往右看和从右往左看完全相同的话，那么就认为这个串是一个 回文串。例如，“abcaacba”是一个回文串，“abcaaba”则不是一个回文串。

　　现在给定若干个字符串，请分别求出它们最长的 回文子序列串 的长度。

【输入格式】

　　若干行，每行每行是一个只含有英文字母的字符串。字符串长度不超过 1000。

【输出格式】

　　每个字符串输出一行一个整数，表示对应字符串的最长回文子序列串的长度。

【输入输出样例】

　Input

abcbdab
bdccaba

　Output

5
4

【数据限制】

　　对于 \(100\%\) 的数据，输入的字符串不超过 50 个。

【来源】

　　Mr.he