# Cut a string

Very easy

Execution time limit is 1 second

Runtime memory usage limit is 128 megabytes

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.

## Examples

Input #1

Answer #1

Submissions 1K

Acceptance rate 47%