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. \includegraphics{https://static.e-olymp.com/content/88/889ab9aed0b8d8d630e6dd4b7803ee9578b9c44f.jpg} Figure 1: the dance platform for Step Step Evolution In the game, you have to obey the following rule: \begin{itemize} \item Except for the beginning of the play, you must not press the arrow panel which is notcorrespond to the edit data. \item The foot must stay upon the panel where it presses last time, and will not be moved untilit’s going to press the next arrow panel. \item The left foot must not step on the panel which locates at right to the panel on which theright foot rests. Conversely, the right foot must not step on the panel which locates at leftto the panel on which the left foot rests. \end{itemize} As for the third condition, the following figure shows the examples of the valid and invalid footsteps. \includegraphics{https://static.e-olymp.com/content/d2/d279081f54b6d708fc41c0c67cb4cda99349b366.jpg} Figure 2: the examples of 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? \InputFile The input consists of several detasets. Each dataset is specified by one line containing a sequence of direction arrows. Directions are described by numbers from \textbf{1} to \textbf{9}, except for 5. The figure below shows the correspondence between numbers and directions. You may assume that the length of the sequence is between \textbf{1} and \textbf{100000}, inclusive. Also, arrows of the same direction won’t appear consecutively in the line. The end of the input is indicated by a single "\textbf{#}". \includegraphics{https://static.e-olymp.com/content/93/93cc8ea1abaae827a603da0c5e215c6d5a66438f.jpg} Figure 3: the correspondence of the numbers to the direction arrows \OutputFile For each dataset, output how many times you have to violate "Natural footstep style" when you play optimally in one line.