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

Містер Б подарував Містеру А рядок $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$ балів): без додаткових обмежень.