Дана строка, состоящая только из цифр. За один ход из этой строки можно удалить любую последовательность подряд идущих одинаковых цифр. Каково минимальное количество ходов, за которое можно удалить всю строку?

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

Одна строка, состоящая из цифр. Длина строки не превышает 300 символов.

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

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