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₁s₂... s_|s|, where record |s| shows the length of the string.

Substring s[i... j] of string s is string s_is_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)² 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⁵). 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.