Mr. A and Palindromes

Mr. B gave Mr. A a string $s$, composed of lowercase Latin letters. The friends defined the "interest" of a non-empty string $t$ as the number of times $t$ appears in the string $s$, multiplied by the length of $t$. Your task is to determine the maximum interest among all non-empty palindromic strings.

A palindrome is a string that reads the same forwards and backwards.

Input

The first line contains the string $s$ $(1\le |s|\le 3\cdot 10^5)$.

Output

Output a single integer — the maximum interest among all non-empty palindromic strings.

Examples

Note

In the first example, the single-letter palindrome "a" appears four times in the string $s$, but the palindrome "abacaba" has the highest interest.

Scoring

1. ($8$ points): $1\le |s|\le 100$;

2. ($15$ points): $1\le |s|\le 1000$;

3. ($24$ points): $1\le |s|\le 10000$;

4. ($26$ points): $1\le |s|\le 100000$;

5. ($27$ points): no additional constraints.