QWERTY Keyboard

Albert wants to type a string of uppercase English letters ('A'-'Z') using a QWERTY keyboard (see the figure above). Albert is not yet used to handling a keyboard, and he has a habit of pressing keys with his left index finger only.

Pressing and releasing a key to type one character takes 1 second, and moving the index finger from one key to an adjacent key takes 2 seconds. While typing the string, the finger always moves only over the keys of the keyboard.

Each key has at most 6 adjacent keys around it. For example, moving the index finger from the S key to A, W, E, D, X, or Z takes 2 seconds.

To type a string, Albert first places his left index finger on the key of the first character of the string, and timing starts from that moment.

To type the string "QWERTY", he can do it in 16 seconds as follows.

• Before typing, move the left index finger onto the Q key. The time this takes is not counted.
• Press and release the Q key to type it, which takes 1 second. (total 1 second)
• Move to the W key, which takes 2 seconds. (total 3 seconds)
• Press and release the W key to type it, which takes 1 second. (total 4 seconds)
• Move to the E key, which takes 2 seconds. (total 6 seconds)
• Press and release the E key to type it, which takes 1 second. (total 7 seconds)
• Move to the R key, which takes 2 seconds. (total 9 seconds)
• Press and release the R key to type it, which takes 1 second. (total 10 seconds)
• Move to the T key, which takes 2 seconds. (total 12 seconds)
• Press and release the T key to type it, which takes 1 second. (total 13 seconds)
• Move to the Y key, which takes 2 seconds. (total 15 seconds)
• Press and release the Y key to type it, which takes 1 second. (total 16 seconds)

As another example, typing the string "LOM" takes 9 seconds.

• Press and release the L key to type it, which takes 1 second. (total 1 second)
• Move to the O key, which takes 2 seconds. (total 3 seconds)
• Press and release the O key to type it, which takes 1 second. (total 4 seconds)
• Move to the M key, which takes 4 seconds. (Moving O -> K -> M is the fastest.) (total 8 seconds)
• Press and release the M key to type it, which takes 1 second. (total 9 seconds)

Given a string consisting only of uppercase English letters ('A'-'Z'), write a program that computes how many seconds Albert needs when he types it as fast as possible.

The first line gives the number of test cases, T.

Each test case is given on one line as a string consisting only of uppercase English letters, with no spaces.

For each test case, print the minimum time needed to type the given string.

• 1 ≤ T ≤ 10
• 2 ≤ length of the string ≤ 100
• Each string contains only uppercase English letters ('A'-'Z').