You are given a string of lowercase Latin letters. Let us define a substring's "occurrence value" as the number of the substring occurrences in the string multiplied by the length of the substring. For a given string find the largest occurrence value of palindromic substrings.

Notes

~|s|~ is the length of string ~s~.
A substring of string ~s_1 s_2 \dots s_{|s|}~ is any non-empty string ~s_i s_{i+1} \dots s_j~, where ~1 \le i \le j \le |s|~. Any string is also its own substring.
A string is called palindromic, if it reads the same in either direction: from left to right and from right to left.

Input Specification

The only line of input contains a non-empty string of lowercase Latin letters (a-z).

Output Specification

Output one integer – the largest occurrence value of palindromic substrings.

Sample Input 1

abacaba

Sample Output 1

7

Explanation for Sample Output 1

There are seven palindromic substrings a, b, c, aba, aca, bacab, abacaba.

• a has 4 occurrences in the given string, its occurrence value is ~4 \times 1 = 4~
• b has 2 occurrences in the given string, its occurrence value is ~2 \times 1 = 2~
• c has 1 occurrence in the given string, its occurrence value is ~1 \times 1 = 1~
• aba has 2 occurrences in the given string, its occurrence value is ~2 \times 3 = 6~
• aca has 1 occurrence in the given string, its occurrence value is ~1 \times 3 = 3~
• bacab has 1 occurrence in the given string, its occurrence value is ~1 \times 5 = 5~
• abacaba has 1 occurrence in the given string, its occurrence value is ~1 \times 7 = 7~

So, the largest occurrence value of palindromic substrings is 7.

Sample Input 2

www

Sample Output 2

4

Scoring

Subtask 1 (points: 8)

~1 \le |s| \le 100~

Subtask 2 (points: 15)

~1 \le |s| \le 1\,000~

Subtask 3 (points: 24)

~1 \le |s| \le 10\,000~

Subtask 4 (points: 26)

~1 \le |s| \le 100\,000~

Subtask 5 (points: 27)

~1 \le |s| \le 300\,000~