Japanese video game company has developed the music video game called Step Step Evolution.
The gameplay of Step Step Evolution is very simple. Players stand on the dance platform, and
step on panels on it according to a sequence of arrows shown in the front screen.

There are eight types of direction arrows in the Step Step Evolution: UP, UPPER RIGHT,
RIGHT, LOWER RIGHT, DOWN, LOWER LEFT, LEFT, and UPPER LEFT. These direction
arrows will scroll upward from the bottom of the screen. When the direction arrow overlaps the
stationary arrow nearby the top, then the player must step on the corresponding arrow panel
on the dance platform. The figure below shows how the dance platform looks like.

In the game, you have to obey the following rule:

• Except for the beginning of the play, you must not press the arrow panel which is not
correspond to the edit data.

• The foot must stay upon the panel where it presses last time, and will not be moved until
it’s going to press the next arrow panel.

• The left foot must not step on the panel which locates at right to the panel on which the
right foot rests. Conversely, the right foot must not step on the panel which locates at left
to the panel on which the left foot rests.

As for the third condition, the following figure shows the examples of the valid and invalid
footsteps.

The first one (left foot for LEFT, right foot for DOWN) and the second one (left foot for LOWER
LEFT, right foot for UPPER LEFT) are valid footstep. The last one (left foot for RIGHT, right
foot for DOWN) is invalid footstep.

Note that, at the beginning of the play, the left foot and right foot can be placed anywhere at
the arrow panel. Also, you can start first step with left foot or right foot, whichever you want.

To play this game in a beautiful way, the play style called “ Natural footstep style” is commonly
known among talented players. “Natural footstep style” is the style in which players make steps
by the left foot and the right foot in turn. However, when a sequence of arrows is difficult,
players are sometimes forced to violate this style.

Now, your friend has created an edit data (the original sequence of direction arrows to be pushed)
for you. You are interested in how many times you have to violate “Natural footstep style” when
you optimally played with this edit data. In other words, what is the minimum number of times
you have to step on two consecutive arrows using the same foot?