eolymp
bolt
Try our new interface for solving problems
Problems

Cut a string

Cut a string

Time limit 1 second
Memory limit 128 MiB

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
Source 2014 KBTU Open, Spring Kazakhstan, Almaty, April 20, Problem J