题目描述

Jerry是一个很强大但是很有爱的人。

Jerry现在有一个字符串，他希望可以将其变成回文串。

但是他现在在工作，于是求助于你，并规定了一些要求。

Jerry的要求是这样的：他想要的回文字符串必须是给定的字符串$S$的某个子序列，并且还是最长的回文串。

例如，Jerry给定的字符串为 acfdcsa ，经过操作后生成出 acdca 。

简化起见，仅需要你给出所生成的回文字符串的长度即可。

注意：

回文串是一个正读和反读都一样的字符串，例如level或acca。

子序列是从最初序列通过去除某些元素但不破坏余下元素的相对位置（在前或在后）而形成的新序列。

输入

输入为一行，即字符串$S$。

数据保证，$1 \leq |S| \leq 10^3$ 且字符均为小写英文字母。

输出

输出一个字符，表示所生成的字符串长度。

样例

asdffglhfa

5