Містер Б подарував Містеру А рядок $s$, що складається з маленьких літер латинського алфавіту. Друзі визначили цікавість непорожньої стрічки $t$, як кількість входжень цієї стрічки $t$ в стрічку $s$ помножена на довжину стрічки $t$. Ваше завдання~--- знайти максимальну цікавість серед всіх непорожніх стрічок які є паліндромами. Паліндромом вважається стрічка що читається однаково з обох сторін. \InputFile Перший рядок містить один рядок $s$ $(1\le |s|\le 3\cdot 10^5)$. \OutputFile Виведіть одне ціле число~--- максимальну цікавість серед всіх непорожніх стрічок які є паліндромами. \Note У першому прикладі паліндром, що складається з однієї літери <<\t{a}>> має чотири входження у рядок $s$, однак найбільшу цікавість має паліндром <<\t{abacaba}>>. \Scoring \begin{enumerate} \item ($8$ балів): $1\le |s|\le 100$; \item ($15$ балів): $1\le |s|\le 1\,000$; \item ($24$ бали): $1\le |s|\le 10\,000$; \item ($26$ балів): $1\le |s|\le 100\,000$; \item ($27$ балів): без додаткових обмежень. \end{enumerate}