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

Вхідні дані

Перший рядок містить один рядок $s$ $(1 \leq ∣ s ∣ \leq 3 \cdot 1 0^{5})$ (1\le |s|\le 3\cdot 10^5).

Вихідні дані

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

Приклади

Приклад 1

Loading

Приклад 2

Loading

Примітка

У першому прикладі паліндром, що складається з однієї літери «a» має чотири входження у рядок $s$ , однак найбільшу цікавість має паліндром «abacaba».

Оцінювання

( $8$ балів): $1 \leq ∣ s ∣ \leq 100$ 1\le |s|\le 100;
( $15$ балів): $1 \leq ∣ s ∣ \leq 1000$ 1\le |s|\le 1\,000;
( $24$ бали): $1 \leq ∣ s ∣ \leq 10000$ 1\le |s|\le 10\,000;
( $26$ балів): $1 \leq ∣ s ∣ \leq 100000$ 1\le |s|\le 100\,000;
( $27$ балів): без додаткових обмежень.