T9 Spelling (Small)

Interview

Time limit5sMemory limit512 MB

Summary

Map each letter of a short message to its keypad digit and repeat count, inserting a space between consecutive letters that share the same key.

Level: Easy2 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 digits. You want to write a message to a friend as the sequence of key presses that types it. Each letter maps to a digit as shown below.

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

Pressing a key once gives the first letter on that key, pressing it twice gives the second letter, and so on. To type b you press 22. To type two letters that sit on the same key one right after the other, you have to wait before pressing that key again. Write the space character ' ' for that wait. So 2 2 means aa while 22 means b.

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 from a to z and space characters. A space is typed by pressing 0.

Limits

1 ≤ N ≤ 100
1 ≤ length of a message ≤ 15

Output

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

Examples1

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