Step Step Evolution

A Japanese game company made the music game Step Step Evolution. The player stands on a dance platform and steps on its panels following the arrows that scroll up the screen.

The game uses eight directions: up, upper right, right, lower right, down, lower left, left, and upper left. Arrows scroll upward from the bottom of the screen, and when an arrow overlaps the fixed arrow near the top, the player steps on the panel for that direction.

Figure 1: the dance platform of Step Step Evolution

While you play, you obey these rules.

• After the play starts, you never press a panel that the arrow data does not ask for.
• A foot stays on the panel it pressed last and does not move until it presses the next panel.
• The left foot never steps on a panel that lies to the right of the panel the right foot rests on. Conversely, the right foot never steps on a panel that lies to the left of the panel the left foot rests on.

Panels are compared by column. Upper left, left, and lower left form the left column, up and down form the middle column, and upper right, right, and lower right form the right column. One panel lies to the right of another only when its column is further right, so two panels in the same column are neither left nor right of each other.

Figure 2: valid and invalid footsteps

In figure 2 the first case (left foot on LEFT, right foot on DOWN) and the second case (left foot on LOWER LEFT, right foot on UPPER LEFT) are valid. The third case (left foot on RIGHT, right foot on DOWN) breaks the rule.

At the start of the play you put the left foot and the right foot on any panels you like, and you press the first arrow with either foot.

Skilled players use the natural footstep style, which alternates the left foot and the right foot. A difficult arrow sequence sometimes forces a player to break it. Given the arrow sequence, find the minimum number of times two consecutive arrows are pressed by the same foot when you play the sequence in the best possible way.

The input holds several datasets. Each dataset is one line with a sequence of arrows. Each direction is written as a digit from 1 to 9 other than 5, laid out like a numeric keypad. 7, 8, and 9 are upper left, up, and upper right, 4 and 6 are left and right, and 1, 2, and 3 are lower left, down, and lower right.

Figure 3: the digit for each direction arrow

The length of a sequence is between 1 and 100000. Inside one sequence the same direction never appears twice in a row. A line holding a single # marks the end of the input.

For each dataset, print in one line the minimum number of times two consecutive arrows are pressed by the same foot.