T9 Spelling | cho.sh

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.