Description

You have the goal of becoming the world’s fastest two-fingered typist. In this problem, your goal is to optimize the movement of your fingers when typing numeric values in order to ensure that you finish typing a number in the shortest amount of time possible. Your numeric keyboard has the following layout:

For convenience, we refer to the cells above according to their row and column; hence, the “5” key is at position (2, 2), and the “0” key takes up both positions (4, 1) and (4, 2). At time 0, your left pointer finger is on the “4” key and your right pointer finger is on the “5” key. During each time interval, each finger may press the key underneath it, move vertically one position, or move horizontally one position. Although both fingers may move simultaneously within a single time interval,

• at most one key may be pressed during any given time interval,
• the left pointer finger’s column must always be less than the right pointer finger’s column at the end of each time interval, and
• both fingers must always be above one of the 10 keys in the diagram at the end of each time interval (e.g., neither finger cannot hover over position (4, 3)).
• The “0” key may be pressed by a finger at either positions (4, 1) or (4, 2).

Examples

• Typing “56” takes three time units. At time 1, both left and right fingers have moved one position to the right and are on keys “5” and “6” respectively. Then, each key is pressed sequentially.
• Typing “71” takes five time units. During the first two time units, the left finger moves up to the “7” and presses the key. However, the right finger is not allowed to be in the same column as the left finger, and hence the left finger takes two time units to get to the “1” key and one time unit to press it.

Input

The input test file will contain multiple test cases. Each test case consists of a single line containing a string of between 1 and 100 digits. The end-of-file is marked by a line containing the word “eof” and should not be processed.

Output

For each input case, output the minimum number of time units required to type the given digits.

56
71
902
eof

3
5
6

Source

Stanford Local 2005