Problems
Cut a string
Cut a string
You are given a string s. It is allowed to take any two same neighbor symbols of this string and delete them. This operation you can do while possible. At the beginning you can choose any symbols from string and delete them. Determine the minimum number of symbols you can delete at the beginning, so that you get the empty string after performing allowed operations.
Input data
One string s of length no more than 100.
Output data
Print the minimum number of symbols you should delete at the beginning.
Examples
Input example #1
abacdeec
Output example #1
2