POLSKI SPOJ

Dany jest wyraz złożony z małych liter alfabetu angielskiego. Na wyrazie tym możemy wykonać dowolną liczbę operacji. Pojedyncza operacja polega na usunięciu dowolnej części wyrazu. Usuwany fragment musi być palindromem. Pozostałe części są sklejane w nowy wyraz z zachowaniem ich dotychczasowej kolejności. Twoim zadaniem jest całkowite usunięcie wyrazu.

Palindrom jest to wyraz, który czytany od lewej strony do prawej brzmi tak samo jak czytany od prawej strony do lewej np. kajak.

Odpowiedz na pytanie, ile minimalnie operacji trzeba wykonać żeby usunąć cały wyraz?

Wejście

Na wejściu znajduje się wyraz złożony z małych liter alfabetu angielskiego, którego długość nie przekracza 400 liter.

Wyjście

Na wyjściu należy wypisać odpowiedź na pytanie, ile minimalnie operacji trzeba wykonać żeby usunąć cały wyraz?

Przykład

Wejście:

addbcba

Wyjście:

2

Wyjaśnienie do przykładu:

W pierwszym kroku usuwamy fragment dd. Po jego usunięciu otrzymujemy wyraz abcba. Ponieważ jest on palindromem możemy go w całości usunąć w drugim kroku.