T9 Spelling (Small)

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.