Mr. A and Palindromes#10501
Sign in

Mr. A and Palindromes

1 second
256 megabytes
Easy

Mr. B gave Mr. A a string , composed of lowercase Latin letters. The friends defined the "interest" of a non-empty string as the number of times appears in the string , multiplied by the length of . 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 (1 \le |s| \le 3 \cdot 10^5).

Output

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

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Note

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

Scoring

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

  2. ( points): 1 \le |s| \le 1\,000;

  3. ( points): 1 \le |s| \le 10\,000;

  4. ( points): 1 \le |s| \le 100\,000;

  5. ( points): no additional constraints.