Description

什么是回文呢？那就是对称的字符串。For example，abcdcba是回文的，abccba也是回文的。那么在一个字符串abccbaabcc，你能找到很多回文的子序列，例如abccba，ccbaabcc，那么最长的就是ccbaabcc，长度为8。

Input

输入一行字符串，由小写英文字母表示，字符长度小于1000。

Output

输出最长回文子序列的长度。

Sample Input

abccbaabcc

Sample Output

8

HINT

Source

wowo1gt