T9 문자 입력 (Small)
면접 대비시간 제한5초메모리 제한512 MB
짧은 메시지의 각 글자를 키패드 숫자와 반복 횟수로 바꾸고, 같은 키를 쓰는 글자가 연달아 나오면 사이에 공백을 넣어 출력한다.
문제
알파벳은 문자가 26개인데 전화기 키패드에는 숫자가 열 개뿐이다. 친구에게 보낼 메시지를 키를 누르는 순서로 적으려고 한다. 각 문자는 아래 표대로 숫자에 대응한다.
키를 한 번 누르면 그 키의 첫 번째 문자, 두 번 누르면 두 번째 문자가 된다. 예를 들어 b를 찍으려면 22를 누른다. 같은 키에 있는 문자를 연달아 찍을 때는 그 키를 다시 누르기 전에 잠깐 기다려야 한다. 이 기다림은 공백 문자 ' '로 적는다. 즉 2 2는 aa를 뜻하고 22는 b를 뜻한다.
입력
첫째 줄에 테스트 케이스의 개수 N이 주어진다. 이어지는 N개의 줄에 메시지가 한 줄에 하나씩 주어진다. 메시지는 소문자 a부터 z까지와 공백 문자로만 이루어진다. 공백은 0을 눌러 찍는다.
제한
- 1 ≤ N ≤ 100
- 1 ≤ 메시지의 길이 ≤ 15
출력
각 테스트 케이스마다 한 줄에 "Case #x: "를 찍고 이어서 그 메시지의 키 누름 순서를 출력한다. x는 1부터 시작하는 테스트 케이스 번호이다.