T9 문자 입력

로마자는 글자가 26개지만 전화기 자판에는 숫자 키가 열 개뿐이다. 친구에게 보낼 메시지를 자판을 누른 순서로 적으려고 한다. 글자는 아래 표대로 숫자 키에 배정되어 있고, 한 글자를 입력하려면 그 글자가 배정된 키를 배정 순서만큼 연달아 누른다. 예를 들어 b는 2번 키에서 두 번째 글자이므로 22를 누른다.

같은 키에 배정된 글자를 연달아 입력할 때는 두 번째 글자를 누르기 전에 잠깐 쉬어야 한다. 쉬는 구간은 공백 문자 하나로 나타낸다. 즉 2 2는 aa이고, 22는 b다. 서로 다른 키를 누를 때는 쉬지 않으므로 공백을 넣지 않는다.

메시지가 주어지면 그 메시지를 입력하는 키 누름 순서를 구하라.

첫째 줄에 테스트 케이스의 수 $N$이 주어진다. 이어서 $N$개의 줄에 메시지가 한 줄에 하나씩 주어진다.

메시지는 소문자 a부터 z까지와 공백 문자로만 이루어진다. 공백은 0번 키를 한 번 눌러 입력한다. 메시지 앞이나 뒤에 오는 공백도 메시지의 일부이므로 그대로 처리한다.

제한

• $1 \le N \le 100$
• $1 \le$ 메시지의 길이 $\le 1000$

각 테스트 케이스마다 Case #x: 다음에 그 메시지를 입력하는 키 누름 순서를 이어 붙여 한 줄에 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호다.