Migrated from Lutece 511 T9

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

T9 is a kind of keyboard used by cellphone all over the world. The normal T9 is like the picture as follow:

For example, if you want to type GALAXY, you should hit the key: 4-2-5-2-9-9.

Given a string only consists of capital letters, you should calculate how many times changing your finger's position if you use your a single finger to type the string on a T9 keyboard.

Input

The first line of input is a single integer $T$($1\leq T\leq 50$), indicates the number of test case.

Then, there are $T$ lines. Each line contains a string only consists of no more than $50$ capital letters.

Output

For each test case, just output one line.

First output Case #C: ,where $C$ is number of test case which is from $1$ to $T$.Then,output a single integer, meaning the times changing your finger's position.

Samples

3
GALAXY
ABC
ADGJM

Case #1: 4
Case #2: 0
Case #3: 4

Resources

pfctgeorge