Обрезка строки

Имеется строка $s$. Разрешается взять два любых одинаковых соседних символа и удалить их из строки. Эту операцию можно производить пока имеется возможность. Сначала Вы можете выбрать любое количество символов в строке и удалить их. Определить наименьшее количество символов, которое Вы можете удалить сначала так, чтобы затем выполняя разрешенную операцию, получить пустую строку.

Входные данные

Содержит строку $s(1\le длина(s)\le 100)$.

Выходные данные

Вывести наименьшее количество символов, которое следует удалить сначала.

Примеры