방언으로 말하기

Google에서는 Googlerese라는 최고의 언어를 고안했다. 텍스트를 Googlerese로 번역하려면 임의의 메시지에서 각 영어 문자를 다른 영어 문자로 바꾼다. 이 대응은 일대일 대응이므로, 같은 입력 문자는 항상 같은 출력 문자로 바뀌고 서로 다른 입력 문자는 항상 서로 다른 출력 문자로 바뀐다. 문자가 자기 자신으로 바뀔 수도 있다. 공백은 그대로 둔다.

예를 들어 (그리고 이것은 힌트다!), 우리의 멋진 번역 알고리즘에는 다음 세 대응이 포함된다: 'a' -> 'y', 'o' -> 'e', 그리고 'z' -> 'q'. 즉, "a zoo"는 "y qee"가 된다.

Googlerese는 가능한 최고의 치환 대응을 기반으로 하며, 우리는 이를 절대 변경하지 않을 것이다. 이는 모든 테스트 케이스에서 항상 동일하다. 문제를 너무 쉽게 만들 수 있으므로 나머지 대응은 알려 주지 않겠지만, 아래에 도움이 될 만한 몇 가지 예제가 있다.

Googlerese로 작성된 텍스트가 주어질 때, 이를 다시 일반 텍스트로 번역할 수 있는가?

이 문제 풀기

일반적으로 Google Code Jam 문제에는 1 소형 입력과 1 대형 입력이 있다. 이 문제에는 1 소형 입력만 있다. 소형 입력을 해결하면 이 문제를 모두 해결한 것이다.

제한

시간 제한: 20초. 메모리 제한: 1GB. 판정 결과가 공개되는 테스트 세트는 하나뿐이다. 1 ≤ T ≤ 30. G는 최대 100개의 문자로 이루어진다. 어떤 텍스트도 올바른 영어임이 보장되지 않는다.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 한 줄에 하나씩 주어진다.

각 줄은 Googlerese 문자열 G로 이루어지며, 이는 문자 'a' - 'z'로 구성된 하나 이상의 단어로 이루어진다. 연속한 단어 사이에는 정확히 하나의 공백 문자(' ')가 있으며, 어떤 줄도 시작이나 끝에 공백이 없다.

각 테스트 케이스마다 "Case #X: S"을 포함하는 한 줄을 출력한다. 여기서 X는 케이스 번호이고 S는 Googlerese로 변환했을 때 G가 되는 문자열이다.