CF356E.Xenia and String Problem

Xenia the coder went to The Olympiad of Informatics and got a string problem. Unfortunately, Xenia isn't fabulous in string algorithms. Help her solve the problem.

String s is a sequence of characters _s_1_s_2... s|s|, where record |s| shows the length of the string.

Substring s[i... j] of string s is string s__i__s__i + 1... s__j.

String s is a Gray string, if it meets the conditions:

• the length of string |s| is odd;
• character occurs exactly once in the string;
• either |s| = 1, or substrings and are the same and are Gray strings.

For example, strings "abacaba", "xzx", "g" are Gray strings and strings "aaa", "xz", "abaxcbc" are not.

The beauty of string p is the sum of the squares of the lengths of all substrings of string p that are Gray strings. In other words, consider all pairs of values i, j (1 ≤ i ≤ j ≤ |p|). If substring p[i... j] is a Gray string, you should add (j - i + 1)2 to the beauty.

Xenia has got string t consisting of lowercase English letters. She is allowed to replace at most one letter of the string by any other English letter. The task is to get a string of maximum beauty.

程序员 Xenia 参加了信息学奥林匹克竞赛，遇到了一道字符串题目。不幸的是，Xenia 在字符串算法方面并不出色。请帮助她解决这个问题。

字符串 $s$ 是一个字符序列 $s_1s_2\ldots s_{|s|}$，其中符号 $|s|$ 表示该字符串的长度。

字符串 $s$ 的子串 $s[i\ldots j]$ 指的是字符串 $s_is_{i+1}\ldots s_j$。

若字符串 $s$ 满足以下条件，则称其为 Gray 字符串：

• 字符串长度 $|s|$ 为奇数；
• 字符 在该字符串中恰好出现一次；
• 要么 $|s| = 1$，要么子串 和 完全相同，且二者均为 Gray 字符串。

例如，字符串 "abacaba"、"xzx"、"g" 是 Gray 字符串，而 "aaa"、"xz"、"abaxcbc" 则不是。

字符串 $p$ 的**美丽值（beauty）**定义为：对 $p$ 的所有 Gray 子串，将其长度的平方求和。换言之，考虑所有满足 $1 \le i \le j \le |p|$ 的下标对 $(i, j)$；若子串 $p[i\ldots j]$ 是 Gray 字符串，则将 $(j - i + 1)^2$ 加入美丽值中。

Xenia 得到了一个由小写英文字母组成的字符串 $t$。她被允许至多修改一个位置上的字符（可替换为任意小写英文字母）。任务是：通过这一操作，使所得字符串的美丽值最大化。

The first line contains a non-empty string t (1 ≤ |t| ≤ 105). String t only consists of lowercase English letters.

第一行包含一个非空字符串 $t$（$1 \leq |t| \leq 10^5$）。字符串 $t$ 仅由小写英文字母组成。

Print the sought maximum beauty value Xenia can get.

Please do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

输出 Xenia 能够获得的最大美丽值。

在 C++ 中，请勿使用 %lld 说明符读取或写入 64 位整数。推荐使用 cin、cout 流，或 %I64d 说明符。

In the first test sample the given string can be transformed into string p = "zbz". Such string contains Gray strings as substrings p[1... 1], p[2... 2], p[3... 3] и p[1... 3]. In total, the beauty of string p gets equal to 12 + 12 + 12 + 32 = 12. You can't obtain a more beautiful string.

In the second test case it is not necessary to perform any operation. The initial string has the maximum possible beauty.

在第一个测试样例中，给定字符串可以被转换为字符串 $p = \text{"zbz"}$。该字符串包含 Gray 子串 $p[1...1]$、$p[2...2]$、$p[3...3]$ 和 $p[1...3]$。字符串 $p$ 的总美观度为 $1^2 + 1^2 + 1^2 + 3^2 = 12$。无法得到更美观的字符串。

在第二个测试样例中，无需执行任何操作。初始字符串已具有最大可能的美观度。