PROGRAMMING:T9 keyboard
After the popularity of iPhone and Android, almost all smart phones are equipped with large screens, which can be used to input text by directly poking the screen with fingers. Before that, the T9 keyboard was the absolute king on the mobile phone that needed to input text through the keyboard.
The general appearance of T9 keyboard, which used to be popular all over the world, is as follows:
If people need to type "galaxy," they need to type in the following order: 4-2-5-2-9-9; When using the keyboard with one hand to input this string, the minimum number of times you need to move your finger is 4 (putting your finger on 4 at the beginning is not included in the number of times you move)
Now I'm going to give you a string containing only capital letters. Please calculate the minimum number of times you need to move your finger to type the string with one hand on the T9 keyboard.
###Input format:
Enter an integer t (T < = 50) in the first line to represent the number of input data groups
Each group of data has one line, and a string s represents the string to be input, which is composed of upper case letters, and the length is not more than 50.
###Output format:
Each group outputs one line; First, output case # C: (C stands for data number, from 1 to t); Output the minimum number of finger movements required to type the string immediately after a space character.
###Input example:
Here is a set of inputs. For example:
```in
three
GALAXY
ABC
ADGJM
```
###Output example:
The corresponding output is given here. For example:
```out
Case #1: 4
Case #2: 0
Case #3: 4
```
answer：If there is no answer, please comment
The general appearance of T9 keyboard, which used to be popular all over the world, is as follows:
If people need to type "galaxy," they need to type in the following order: 4-2-5-2-9-9; When using the keyboard with one hand to input this string, the minimum number of times you need to move your finger is 4 (putting your finger on 4 at the beginning is not included in the number of times you move)
Now I'm going to give you a string containing only capital letters. Please calculate the minimum number of times you need to move your finger to type the string with one hand on the T9 keyboard.
###Input format:
Enter an integer t (T < = 50) in the first line to represent the number of input data groups
Each group of data has one line, and a string s represents the string to be input, which is composed of upper case letters, and the length is not more than 50.
###Output format:
Each group outputs one line; First, output case # C: (C stands for data number, from 1 to t); Output the minimum number of finger movements required to type the string immediately after a space character.
###Input example:
Here is a set of inputs. For example:
```in
three
GALAXY
ABC
ADGJM
```
###Output example:
The corresponding output is given here. For example:
```out
Case #1: 4
Case #2: 0
Case #3: 4
```
answer：If there is no answer, please comment