You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

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.