题目描述

小 X 有一个仅由小写字母组成的字符串，他可以选择对字符串执行以下操作之一：
    将字符串中某个位置上的字符替换为另一个小写字母；
    什么也不做（不修改字符串）。
小 X 想知道，上述操作择其一进行后，字符串中回文子串的个数最多是多少？

回文是指字符串正读和反读完全一致；
子串是指从原始字符串中截取的一段连续的、保持原有字符顺序的字符序列，字符串本身也看作自己的子串；
回文子串按位置计数：内容相同但起始/结束位置不同的子串，都计入总数。

输入格式

输入仅有一行，包含一个字符串，字符串长度最多为 5000。

输出格式

输出一个整数，表示按规则能得到回文子串的最多个数。

样例数据

input1

abcda

output1

7

说明1

小 X 可以将字符串修改为 abada，这样回文子串共有 7 个，分别为 a, b, a, d, a, aba, ada。

input2

abcccba

output2

13

数据范围与提示

10%：字符串长度为2；
30%：字符串长度不超过50；
60%：字符串长度不超过200；
80%：字符串长度不超过1000；
100%：字符串长度不超过5000。