Містер Б подарував Містеру А рядок s, що складається з маленьких літер латинського алфавіту. Друзі визначили цікавість непорожньої стрічки t, як кількість входжень цієї стрічки t в стрічку s помножена на довжину стрічки t. Ваше завдання — знайти максимальну цікавість серед всіх непорожніх стрічок які є паліндромами.
Паліндромом вважається стрічка що читається однаково з обох сторін.
Перший рядок містить один рядок s (1≤∣s∣≤3⋅105).
Виведіть одне ціле число — максимальну цікавість серед всіх непорожніх стрічок які є паліндромами.
У першому прикладі паліндром, що складається з однієї літери «a
» має чотири входження у рядок s, однак найбільшу цікавість має паліндром «abacaba
».
(8 балів): 1≤∣s∣≤100;
(15 балів): 1≤∣s∣≤1000;
(24 бали): 1≤∣s∣≤10000;
(26 балів): 1≤∣s∣≤100000;
(27 балів): без додаткових обмежень.