Шаг Шаг Эволюция
Японская компания по разработке видеоигр выпустила музыкальную игру под названием Step Step Evolution. Игровой процесс в этой игре очень прост: игроки стоят на танцевальной платформе и наступают на панели в соответствии с последовательностью стрелок, отображаемых на экране перед ними.
В Step Step Evolution есть восемь типов направлений стрелок: ВВЕРХ, ВВЕРХ-ПРАВО, ПРАВО, ВНИЗ-ПРАВО, ВНИЗ, ВНИЗ-ЛЕВО, ЛЕВО и ВВЕРХ-ЛЕВО. Эти стрелки движутся вверх от нижней части экрана. Когда стрелка достигает неподвижной стрелки в верхней части экрана, игрок должен наступить на соответствующую панель на танцевальной платформе. На рисунке ниже показана танцевальная платформа.
Рисунок 1: танцевальная платформа для Step Step Evolution
В игре необходимо соблюдать следующие правила:
За исключением начала игры, нельзя нажимать на панель, которая не соответствует текущей стрелке.
Нога должна оставаться на панели, на которую она наступила в последний раз, и не перемещаться, пока не будет нажата следующая панель.
Левая нога не должна наступать на панель, расположенную справа от панели, на которой стоит правая нога, и наоборот, правая нога не должна наступать на панель, расположенную слева от панели, на которой стоит левая нога.
Для третьего условия на следующем рисунке показаны примеры допустимых и недопустимых шагов.
Рисунок 2: примеры допустимых и недопустимых шагов
Первый (левая нога на ЛЕВО, правая нога на ВНИЗ) и второй (левая нога на ВНИЗ-ЛЕВО, правая нога на ВВЕРХ-ЛЕВО) шаги допустимы. Последний (левая нога на ПРАВО, правая нога на ВНИЗ) шаг недопустим.
Обратите внимание, что в начале игры левая и правая нога могут быть размещены в любом месте на панели стрелок. Вы можете начать первый шаг с любой ноги по вашему выбору.
Среди опытных игроков популярен стиль игры, называемый "Естественный стиль шагов". Это стиль, при котором игроки чередуют шаги левой и правой ногой. Однако, если последовательность стрелок сложная, игроки иногда вынуждены отступать от этого стиля.
Теперь ваш друг создал для вас последовательность стрелок, которые нужно нажать. Вам интересно, сколько раз вам придется нарушить "Естественный стиль шагов", играя оптимально с этой последовательностью. Иными словами, какое минимальное количество раз вам придется наступить на две последовательные стрелки одной и той же ногой?
Входные данные
Входные данные состоят из нескольких наборов. Каждый набор представлен одной строкой, содержащей последовательность стрелок. Направления обозначены числами от 1 до 9, за исключением 5. На рисунке ниже показано соответствие между числами и направлениями.
Вы можете предположить, что длина последовательности находится в диапазоне от 1 до 100000 включительно. Стрелки одного и того же направления не будут идти подряд. Конец ввода обозначается одиночным символом "#".
Рисунок 3: соответствие чисел стрелкам направления
Выходные данные
Для каждого набора данных выведите, сколько раз вам придется нарушить "Естественный стиль шагов" при оптимальной игре, в отдельной строке.