A9231 | 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.

The first line contains a non-empty string $t$ $(1<=|t|<=10^{5})$ . String $t$ only consists of lowercase English letters.

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.