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.

Input data

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 100.

Output data

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

Examples

PALIN.IN

anaban

PALIN.OUT

2
PALIN.IN

abaccbcb

PALIN.OUT

3
PALIN.IN

anavolimilana

PALIN.OUT

5

Explanations:

#1: a_naban
#2: aba_cc_bcb
#3: ana_v_o_limil_ana