Background

最长双回文子序列

Description

给定一个字符串 s，请找出其中最长的 "双回文子序列" 的长度。"双回文子序列" 是指一个非空的子序列 T，它可以被分割成两个非空的连续部分 T1 和 T2（即 T = T1 + T2，T1 和 T2 均不为空），且 T1 和 T2 都是回文子序列。

Input

输入一行包含一个只由小写英文字母组成的字符串 s（1 ≤ len(s) ≤ 1000）。

Output

输出一个整数，表示最长双回文子序列的长度。如果不存在这样的子序列（例如字符串长度小于 2），则输出 0。

Samples

abba

4

Limitation

1s, 1024KiB for each test case.