Code Lock

The lock you use opens with a code made of letters instead of a key. The lock consists of a row of wheels, and each wheel is engraved with the 26 lowercase English letters from 'a' to 'z' in order.

Turning a wheel up by one step changes the displayed letter to the next letter of the alphabet (if it was showing the last letter 'z', it becomes 'a'). Turning a wheel down by one step changes the displayed letter to the previous letter of the alphabet (if it was showing the first letter 'a', it becomes 'z').

You may also turn any group of adjacent, contiguous wheels in the same direction with a single movement. The effect is the same as turning each wheel in that group one step in that direction, but it is done in one movement instead of one wheel at a time.

The lock opens when the wheels display a fixed secret string. Right now every wheel shows the letter 'a'. Find the minimum number of movements needed to open the lock.

The input consists of several test cases. Each test case is given on a single line as one nonempty string of at most 1000 lowercase letters. This string is the secret string that opens the lock.

The line following the last test case contains a single asterisk ('*').

For each test case, output on its own line a single integer: the minimum number of movements needed to open the lock.