T9 Spelling

Interview

Time limit5sMemory limit512 MB

Summary

Given messages, output the keypad press sequences that type them, inserting a space between consecutive presses on the same key.

Level: Easy3 of 10
Topics: String, Implementation, Hash map, Simulation
Solved: No attempts yet

Problem

The Latin alphabet has 26 letters, but a telephone keypad has only ten digit keys. You want to write a message to a friend as the sequence of key presses that types it. Letters are assigned to digits as in the table below, and you type a letter by pressing its key as many times as its position on that key. For example, b is the second letter on key 2, so you press 22.

Key	Letters
2	a, b, c
3	d, e, f
4	g, h, i
5	j, k, l
6	m, n, o
7	p, q, r, s
8	t, u, v
9	w, x, y, z
0	space

To type two letters that sit on the same key in a row, you have to pause before pressing the key again. Write one space character for that pause. So 2 2 types aa, while 22 types b. Pressing two different keys needs no pause, so no space goes between them.

Given a message, find the sequence of key presses that types it.

Input

The first line contains the number of test cases $N$ . Each of the next $N$ lines contains one message.

A message consists only of lowercase letters a to z and space characters. A space is typed with one press of key 0. Spaces at the start or the end of a message are part of the message and are typed like any other space.

Limits

$1 \le N \le 100$
$1 \le$ length of a message $\le 1000$

Output

For each test case, print one line containing Case #x: followed by the sequence of key presses that types the message. Here $x$ is the test case number, starting at 1.

Examples4

Example 1

Input

4
hi
yes
foo  bar
hello world

Expected output

Case #1: 44 444
Case #2: 999337777
Case #3: 333666 6660 022 2777
Case #4: 4433555 555666096667775553

Example 2

Input

1
abcdefghijklmnopqrstuvwxyz

Expected output

Case #1: 2 22 2223 33 3334 44 4445 55 5556 66 6667 77 777 77778 88 8889 99 999 9999

Example 3
Input
```
1
 
```
Expected output
```
Case #1: 0
```

Example 4

Input

3
a
z
s

Expected output

Case #1: 2
Case #2: 9999
Case #3: 7777