암호화된 문자 메시지

과학 위원회 위원들은 이메일로 문제를 논의하고, 암호로 보호된 압축 파일을 서로 주고받는다. 이메일은 안전한 통신 수단이 아니기 때문에 각 파일의 암호는 SMS(문자 메시지)로 전달하며, 안전성을 높이기 위해 암호는 보내기 전에 암호화한다. 암호화 방식은 옛날 휴대폰에서 쓰던 멀티탭(multi-tap) 문자 입력 방식을 기반으로 한다.

멀티탭에서는 한 글자를 입력하기 위해 키를 한 번 이상 누른다. 각 키에서 첫 번째 글자는 1번, 두 번째 글자는 2번, 세 번째 글자는 3번 누르면 나온다. 예를 들어 2 키를 한 번 누르면 A, 두 번 누르면 B, 세 번 누르면 C가 된다.

키패드는 26개의 알파벳을 2번부터 9번 키에 다음과 같이 배치한다:

암호의 $i$번째 문자(위치는 $1$부터 센다)를 암호화하려면, 그 문자를 만드는 키를 원래 필요한 횟수보다 $i$번 더 누른다. 어떤 키의 마지막 문자를 지나치면 다시 그 키의 첫 문자로 돌아오므로, 누름은 같은 키 안에서 순환한다. 이렇게 도달한 문자가 암호화된 문자이며, 원래 문자와 같은 대소문자(대문자 또는 소문자)를 가진다. 예를 들어 암호의 4번째 문자가 U라면, U가 있는 8 키(T, U, V)를 $2 + 4 = 6$번 누른다. T→U→V→T→U→V로 순환하므로 6번째 누름은 V에 도달하고, 따라서 U는 V로 암호화된다.

암호화된 암호가 주어질 때, 원래 암호를 복원하라.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 한 줄로 주어지며, 암호화된 암호 하나, 즉 길이가 100 이하인 비어 있지 않은 영문자(대문자 또는 소문자) 문자열이다. 입력의 마지막 줄에는 # 한 글자만 주어진다.

각 테스트 케이스마다 복호화된(원래) 암호를 한 줄에 출력한다. 암호는 대소문자를 구분하므로 모든 문자의 대소문자를 그대로 유지해야 한다.