该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

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

Format

Input

输入一个字符串

Output

输出其最长子序列的长度

Samples

132542351

7

Limitation

1s, 1024KiB for each test case.