Мистер А и палиндромы

Мистер Б подарил Мистеру А строку $s$, состоящую из строчных букв латинского алфавита. Друзья решили определить интерес непустой строки $t$ как произведение количества вхождений строки $t$ в строку $s$ на длину строки $t$. Ваша задача — найти максимальный интерес среди всех непустых строк, которые являются палиндромами.

Палиндром — это строка, которая читается одинаково слева направо и справа налево.

Входные данные

Первая строка содержит строку $s$ $(1\le |s|\le 3\cdot 10^5)$.

Выходные данные

Выведите одно целое число — максимальный интерес среди всех непустых строк, которые являются палиндромами.

Примеры

Примечание

В первом примере палиндром, состоящий из одной буквы «a», встречается в строке $s$ четыре раза, но наибольший интерес имеет палиндром «abacaba».

Оценивание

1. ($8$ баллов): $1\le |s|\le 100$;

2. ($15$ баллов): $1\le |s|\le 1000$;

3. ($24$ балла): $1\le |s|\le 10000$;

4. ($26$ баллов): $1\le |s|\le 100000$;

5. ($27$ баллов): без дополнительных ограничений.