You just achieved the High Score on your favorite video game! Now, you get to enter your name! You have to use the controller to enter your name, which can be awkward.

Here’s how it works:

• There are only the 26 capital letters A to Z, in order. There are no numbers, spaces, lower case letters, or any other characters.
• Pushing UP or DOWN changes the active letter one letter forward (UP) or backward (DOWN). The active letter starts at A. It will not reset when you move around in the name. It also wraps: UP from Z goes to A, DOWN from A goes to Z.
• Pushing LEFT or RIGHT moves the cursor one letter left or right in the current name. Note that once the cursor is at either end of the current name, it cannot move any further in that direction.
• Pushing the FIRE button adds the active letter to the name.

Input

There will be several test cases in the input. Each test case will consist of a single string on its own line, with from 1 to 18 capital letters, representing a name that must be entered into the High Score list. The input will end with a line with a single 0.

Output

For each test case, output a single integer representing the smallest number of button pushes needed to enter the name. Output no spaces, and do not separate answers with blank lines.

Example

Input:
ALMA
YES
0

Output:
17
21