Нека збор во оваа задача значи низа од неколку мали букви од англиската азбука. Палиндром пак е збор кој се чита исто од почеток кон крај и од крај кон почеток. На пример, палиндроми се: potop, rotor, anasana.

За еден збор велиме дека е k-палиндромен ако од сите негови подзборови точно k се палиндроми.

Формално, нека w е збор со должина n. Подзборот w_a,b се добива со земање на сите последователни букви од зборот w кои се наоѓаат од позиција a до позиција b во зборот. Бројот k се дефинира како бројот на различни парови a, b (1 ≤ a ≤ b ≤ n) за кои подзборот w_a,b е палиндром.

Вам ви е даден зборот w. Имате право да промените една од буквите во зборот (која сакате - во која сакате), или пак да го оставите зборот како што е. Евентуалната промена на буква треба да е таква што k ќе биде максимално можно. Најдете го k за променетиот збор w.

Влез

Во првиот ред е запишан еден збор.

Забелешка.
Нека n е должина на влезниот збор.
Во подзадача 1, за 19 поени: 1 ≤ n ≤ 100.
Во подзадача 2, за 29 поени: 101 ≤ n ≤ 5 000.
Во подзадача 3, за 52 поени: 5001 ≤ n ≤ 100 000

Излез

Отпечатете го бараното k.

Ограничувања

Временско ограничување: 300 milliseconds
Мемориско ограничување: 256 megabytes

Примери

влез
uuu

излез
6

влез
xbiix

излез
9

влез
mendo

излез
6

Објаснување на првиот пример: Сите поднизи се веќе палиндроми па најдобро е да не менуваме ништо.

Објаснување на вториот пример: Ќе ја смениме втората буква во “i”, па ќе го добиеме “xiiix” со k = 9.