Keitai Message

Interview

Time limit8sMemory limit512 MB

Summary

Given a sequence of key presses, decode it by grouping repeated digits and mapping each group to a character via the phone keypad.

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

Problem

Alice is trying to send Miku a message on her cell phone.

The only buttons available for input on the cell phone are the number buttons. So to enter characters, she presses number buttons several times. The number buttons on the cell phone are assigned the following characters, and button 0 is assigned the confirm button. On this cell phone, the confirm button must be pressed after finishing the input of one character.

1: . , ! ? (space)
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: confirm button

For example, pressing button 2, button 2, button 0 changes the character 'a' → 'b', and since the confirm button is pressed here, the character b is output. Entering the same digit repeatedly cycles the character. That is, pressing button 2 five times and then button 0 changes the character 'a' → 'b' → 'c' → 'a' → 'b', and since the confirm button is pressed here, 'b' is output.

It is possible to press the confirm button when no button has been pressed, but in that case no character is output.

Your job is to reconstruct the message Alice made from the sequence of buttons she pressed.

Input

The first line gives the number of test cases. Then, for each test case, a digit string of length at most 1024 is given on one line.

Output

For each test case, output the string of the message Alice made, one line per test case. You may assume the output is at least 1 character and fewer than 76 characters.

Examples1

Example 1

Input

5
20
220
222220
44033055505550666011011111090666077705550301110
000555555550000330000444000080000200004440000

Expected output

a
b
b
hello, world!
keitai