Дано рядок, який складається лише з цифр. За один хід з цього рядка можна видалити довільну послідовність підряд ідучих однакових цифр. Яка мінімальна кількість ходів, за яку можна видалити весь рядок?

Вхідні дані

Один рядок, який складається лише з цифр. Довжина рядка не перевищує 300 символів.

Вихідні дані

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