The Latin alphabet contains 26 characters and telephones
only have ten digits on the keypad. We would like to make it
easier to write a message to your friend using a sequence of
keypresses to indicate the desired characters. The letters are
mapped onto the digits as shown below. To insert the character
‘B’ for instance, the program would press “22”. In order to
insert two characters in sequence from the same key, the user
must pause before pressing the key a second time. The space
character ‘ ’ should be printed to indicate a pause. For
example, “2 2” indicates “AA” whereas “22” indicates “B”.
Figure 1: Phone keypad
The first line of input gives the number of cases,
$N, 1 \leq N \leq 100$.
$N$ test cases follow.
Each case is a line of text containing the desired message,
which will be at most $1000$ characters long. Each message
will consist of only lowercase characters ‘a’–‘z’ and space
characters ‘ ’. Pressing zero emits a space.
For each test case, output one line containing “Case
#$x$: ” followed by the
message translated into the sequence of key presses.
|Sample Input 1
||Sample Output 1
Case #1: 44 444
Case #2: 999337777
Case #3: 333666 6660 022 2777
Case #4: 4433555 555666096667775553