You are given a string of lower-case Latin letters. Let us define 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.

Input

The only line of input contains a non-empty string S of lower-case Latin letters (a-z), |S| <= 300,000.

Output

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

Example

Input:
abacaba

Output:
7