Вдоль веревки слева направо расположено n шариков красного и синего цветов. Эти воздушные шары представлены строкой s из n символов.
Если i-й символ s равен 0, i-ый шарик слева окрашивается в красный цвет, если он равен 1, он окрашивается в синий цвет.
Вы должны перекрасить некоторые из этих воздушных шаров, чтобы не было соседних воздушных шаров одного цвета. Какое наименьшее количество шаров следует перекрасить?
Одна строка s (1 ≤ |s| ≤ 10^5
), представляющая цвета шаров. Через |s| обозначена длина строки s.
Выведите минимальное количество шаров, которое нужно перекрасить, чтобы выполнить условие задачи.
В первом тесте условие задачи можно выполнить, покрасив средний (второй) шар в синий цвет.
Во втором тесте нет необходимости красить шары.