Jasio nadal kontynuuje swoją wielką kampanię w ulubionej grze strategicznej. Wciąż toczy zaciętą walkę z potężnym Zbójem i czuje, że powoli traci przewagę. Jak do tej pory, szpiedzy Jasia bezskutecznie próbują przedostać się do wiosek przeciwnika i zdobyć informacje, które pozwoliłyby naszemu bohaterowi pokonać wroga. Problem jest tego typu, że gdy szpieg zbliża się do bram wioski, słyszy pewne niezrozumiałe słowo i żeby wejść do środka musi prawidłowo podać pasujące do słowa hasło. Jasiu dowiedział się z pewnego źródła, że Zbój cierpi na chorobę, która się zwie "aibohphobia" - lęk przed palindromami. Palindrom to wyrażenie brzmiące tak samo czytane od lewej do prawej i od prawej do lewej np.:

"a kilku klika", "asa loguj u golasa" czy "julu, mysz sama, masz, symuluj". 

Z innego źródła dowiedział się, że hasłem może być liczba, która reprezentuje ilość liter najdłuższego podciągu, który jest palindromem.

Pomóż ponownie naszemu strategowi i napisz program, który być może rozwiąże wszystkie problemy Jasia.

Wejście

Nieokreślona ilość wierszy. Każdy wiersz składa się z n małych liter języka angielskiego (n ≤ 10⁴). 

Wyjście

Dla każdego wiersza jedna liczba określająca ilość znaków przypadająca na najdłuższy palindrom spełniający kryteria zadania.

Przykład

Input:
algoliga
kokosek
macbon
witman
damians
adambak
narbej
mrozik
mariosoft
kaspro

Output:
5
5
1
1
3
3
1
1
3
1