Given a string consisting of uppercase Latin letters. It is possible to remove from this string all pairs of adjacent identical letters, including pairs formed after deleting other pairs. You need to replace 0 or more letters in the given string so that after deleting all pairs, the string becomes empty.
Input:
The first line contains one string of even length from 2 to 200, consisting of lowercase Latin letters.
Output:
In the first line print the minimum number of letter replacements.
Example:
Explanation:
You can replace the sixth letter with b, then the removal process will look like this: baddabcc -> baddab-> baab-> bb-> .