Description

Una palabra se dice palíndromo si la misma palabra es exactamente idéntica al derecho y al revés como por ejemplo 'ABA', 'AA', 'A' y 'CASAC'. Por otra parte cualquier secuencia de caracteres puede ser vista como 1 o más secuencias de palíndromos concatenadas. Por ejemplo ‘guapa’ es la concatenación de los palíndromos ‘g’, ‘u’ y ‘apa’; o ‘casacolorada’ es la concatenación de ‘casac’, ‘olo’, ‘r’, ‘ada’. El problema consiste dado una palabra de a lo máximo 2000 letras minúsculas, imprime el número mínimo de palabras palíndromas en que se puede dividir.

Input

La entrada consiste de una línea por caso, cada línea contiene una cadena s de entre 1 y 2000 caracteres. La entrada termina con EOF. Puedes estar seguro que la entrada no contiene más de 1000 casos.

Output

Por cada caso imprime el número mínimo de palabras palíndromas en que se puede dividir s.

casacolorada
casac
hola

4
1
4

Problemsetter: Gabriel Filiberto López Pérez