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 1000$

Subtask 3 (points: 24)

$1\le |s|\le 10000$

Subtask 4 (points: 26)

$1\le |s|\le 100000$

Subtask 5 (points: 27)

$1\le |s|\le 300000$