High Score

Time limit1sMemory limit128 MB

Summary

Compute the minimum joystick moves (up/down letter changes and left/right cursor moves, with wraparound) needed to type a target uppercase string starting from all 'A's.

Level: Medium6 of 10
Topics: Greedy, String, Implementation
Solved: No attempts yet

Problem

Hyunsu is playing a game in which a joystick guides a worm out of a maze. When the highest score is reached, the player must type their name with the joystick. The rules for typing the name are as follows.

At the start, the name shown on the screen consists entirely of the letter 'A', and the first character is selected.
Moving the joystick up changes the currently selected letter to the next letter of the alphabet, and moving it down changes it to the previous letter. The letter after 'Z' is 'A', and the letter before 'A' is 'Z'.
Moving the joystick left selects the character immediately to the left of the current one, and moving it right selects the character immediately to the right. Moving left while the leftmost character is selected selects the rightmost character, and moving right while the rightmost character is selected selects the leftmost character.

Hyunsu wants to finish typing the desired name using as few joystick moves as possible. Given the name to type, find the minimum number of joystick moves required to complete it. The length of the name to type equals the length of the name initially shown on the screen, and it does not matter which character is selected at the end.

Input

The first line contains the number of test cases $T$ . ( $1 \le T \le 100$ )

Each test case consists of a single line containing the name Hyunsu wants to type. The name consists only of uppercase letters and has length at most $1000$ .

Output

For each test case, print on its own line the minimum number of joystick moves needed to complete the name.

Examples5

Example 1
Input
```
2
JEROEN
JAN
```
Expected output
```
56
23
```
Example 2
Input
```
1
AAAA
```
Expected output
```
0
```
Example 3
Input
```
1
B
```
Expected output
```
1
```
Example 4
Input
```
1
BBBB
```
Expected output
```
7
```
Example 5
Input
```
1
AAB
```
Expected output
```
2
```