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

One string s of length no more than 100.

Output

Print the minimum number of symbols you should delete at the beginning.