编码员 Xenia 参加了信息学奥林匹克竞赛并遇到了字符串问题。不幸的是,Xenia 在字符串算法方面并不出色。帮助她解决问题。
字符串 s 是字符序列 s1s2... s|s|,其中记录 |s|显示字符串的长度。
字符串 s 的子字符串 s[i... j] 是字符串 sisi + 1... sj。
字符串 s 是灰字符串,如果满足条件:
- 字符串 |s| 的长度是奇数;
- 字符 $$S^{\frac{|s|+1}{2}}$$ 在字符串中只出现一次;
- 任一 |s| = 1,或子字符串 $$s[1 \ldots \frac{|s|+1}{2}-1]$$ 和 $$s \left[ \frac{|s|+1}{2} + 1 \ldots |s| \right]$$ 相同,都是灰色字符串。
例如,字符串“abacaba”、“xzx”、“g”是灰色字符串,而字符串“aaa”、“xz”、“abaxcbc”则不是。
字符串 p 的美妙之处在于字符串 p 中所有灰字符串子串的长度平方和。换句话说,考虑所有值对 i, j (1 ≤ i ≤ j ≤ |p|)。如果子串p[i...j]是灰串,则应在美度上加上(j - i + 1)2。
Xenia 得到由小写英文字母组成的字符串 t。她最多可以用任何其他英文字母替换字符串中的一个字母。任务是获得最美丽的字符串。
输入
第一行包含一个非空字符串 t (1 ≤ |t| ≤ 105)。字符串t仅由小写英文字母组成。
输出
打印 Xenia 可以获得的最大美丽值。
请不要使用 %lld 说明符在 С++ 中读取或写入 64 位整数。最好使用 cin、cout 流或 %I64d 说明符。
示例
输入 #1
zzz
输出 #1
12
输入 #2
aba
输出 #2
12
输入 #3
abacaba
输出 #3
83
输入#4
aaaaaa
输出#4
15
注意
在第一个测试样本中,给定的字符串可以转换为字符串 p = "zbz"。该字符串包含灰色字符串作为子字符串 p[1... 1]、p[2... 2]、p[3... 3] 和 p[1... 3]。总的来说,字符串 p 的美观度等于 12 + 12 + 12 + 32 = 12。您无法获得更漂亮的字符串。
在第二个测试用例中,无需执行任何操作。初始字符串具有最大可能的美感。