Encuentra el largo de la subsecuencia más larga de \(s\) que es un palíndromo (se borran caracteres de \(s\) sin cambiar el orden de los demás).

Entrada

Una línea con \(s\), de entre \(1\) y \(1000\) letras minúsculas.

Salida

El largo de la subsecuencia palíndroma más larga.

Ejemplo 1

Entrada

bbbab

Salida

4

Ejemplo 2

Entrada

cbbd

Salida

2

Ejemplo 3

Entrada

a

Salida

1