PALIN

문제

A palindrome is a word that is read the same forward or backwards. If a word is not a palindrome, it can be cut into parts that are palindromes. Write a program that will calculate the smallest number of palindrome parts to which a given sequence of characters can be cut.

입력

The first and only line of input file contains a sequence of characters. The characters used as input will be from the set of small letters of English alphabet (a–z). The length of every input sequence will be at most 2000.

출력

The first and only line of output file should contain required number of palindromes.