Description

回文是指正序与逆序相同的飞空字符串。比如civic，racecar自身都是自己的最长回文子序列。比如character的最长回文子序列为carac。

Format

Input

输入一个字符串

Output

输出其最长子序列的长度

Samples

132542351

7

Limitation

1s, 1024KiB for each test case.