Mister A və palindromlar

Mister B, Mister A-ya kiçik latın hərflərindən ibarət $s$ sətirini hədiyyə etdi. Dostlar, boş olmayan $t$ sətirinin maraqlılığını, bu sətirin $s$ sətirindəki daxilolmalarının sayını $t$ sətirinin uzunluğuna vuraraq hesablayırlar. Sizin vəzifəniz — palindrom olan bütün boş olmayan sətirlər arasında maksimum maraqlılığı tapmaqdır.

Palindrom, hər iki tərəfdən eyni oxunan sətirə deyilir.

Giriş verilənləri

Birinci sətir, $s$ $(1\le |s|\le 3\cdot 10^5)$ sətirini ehtiva edir.

Çıxış verilənləri

Bir tam ədəd çıxarın — palindrom olan bütün boş olmayan sətirlər arasında maksimum maraqlılıq.

Nümunələr

Qeyd

Birinci nümunədə, bir hərfdən ibarət olan «a» palindromu $s$ sətirində dörd dəfə daxil olur, lakin ən böyük maraqlılığa «abacaba» palindromu malikdir.

Qiymətləndirmə

1. ($8$ bal): $1\le |s|\le 100$;

2. ($15$ bal): $1\le |s|\le 1000$;

3. ($24$ bal): $1\le |s|\le 10000$;

4. ($26$ bal): $1\le |s|\le 100000$;

5. ($27$ bal): əlavə məhdudiyyətlər olmadan.