R.Ø.L.P. 암호 바퀴

토미와 호랑이는 비밀 클럽 R.Ø.L.P.를 운영합니다. 이 클럽의 목적은 숙적 수산네에 맞서 그녀의 삶을 최대한 비참하게 만드는 것입니다. 여느 비밀 클럽처럼 R.Ø.L.P.에도 비밀 클럽하우스, 비밀 암호, 모든 회원이 외워야 하는 비밀 노래, 비밀 회원 명단 등이 있습니다. 수산네가 자기들의 계획을 알아채지 못하도록, 클럽은 모든 계획을 적을 때 사용하는 비밀 코드도 가지고 있습니다. 암호화된 메시지는 클럽하우스의 안전한 곳에 보관됩니다.

이 비밀 코드는 암호 바퀴(code wheel)에 기반합니다. 바깥쪽 고정 바퀴의 가장자리에는 사용할 수 있는 모든 문자가 다음 순서로, 총 42개 적혀 있습니다: 알파벳 A부터 Å까지 29자(A B C D E F G H I J K L M N O P Q R S T U V W X Y Z Æ Ø Å), 그다음 공백 문자, 쉼표(,), 마침표(.), 마지막으로 숫자 0 1 2 3 4 5 6 7 8 9. 바깥쪽 바퀴 안쪽에는 똑같은 문자들이 같은 순서로 적힌, 조금 더 작은 회전 가능한 바퀴가 바깥쪽 바퀴에 정렬되어 들어 있습니다.

메시지를 암호화하려면 안쪽 바퀴를 임의의 위치로 돌립니다. 그런 다음 메시지의 각 문자를 바깥쪽 바퀴에서 찾아, 그 바로 안쪽에 있는 안쪽 바퀴의 문자로 바꿉니다. 반대로 메시지를 복호화하려면 먼저 안쪽 바퀴가 어느 위치에 있었는지 알아야 하며, 암호문의 각 문자를 안쪽 바퀴에서 찾아 그 바로 바깥쪽에 있는 바깥쪽 바퀴의 문자로 바꿉니다.

예를 들어 그림과 같이 바퀴가 맞춰져 있으면 TOMMY OG TIGEREN이라는 글은 NIGGSXIAXNCA8L8H로 암호화됩니다.

안타깝게도 수산네는 토미와 호랑이가 무슨 꿍꿍이를 꾸미는지 관심을 갖기 시작했습니다. 약간의 조사 끝에 그녀는 비밀 클럽하우스를 찾아냈고, 그곳에서 암호문 형태의 모든 비밀 계획을 발견해 베껴 적었습니다. 게다가 그 암호 바퀴가 들어 있는 시리얼을 만드는 회사가 수산네가 가장 좋아하는 시리얼도 만드는데, 판매를 늘리려고 그 시리얼에도 R.Ø.L.P.가 쓰는 것과 똑같은 암호 바퀴를 넣었습니다. 이제 수산네는 비밀 계획을 밝혀낼 모든 것을 손에 넣었고, 각 메시지를 어떻게 복호화할지만 알아내면 됩니다.

훌륭한 아마추어 탐정인 수산네는 글자 조합 RØLP가 모든 메시지에 높은 확률로 들어 있으리라고 추측했습니다. 당신이 "컴퓨터 전문가"이므로, 수산네는 암호문을 자동으로 복호화해 평문으로 출력하는 프로그램을 만들어 주길 바랍니다. 복호화 결과에 글자 조합 RØLP가 나타나면 그 메시지를 올바르게 복호화한 것입니다. RØLP가 나오는 복호화를 하나도 찾지 못하면 그 사실을 알려야 합니다. 한 메시지에 대해 복호화가 여러 개 나올 수도 있는데, 그럴 때는 가능한 복호화를 모두 출력하고 어느 것이 맞는지는 수산네가 판단하도록 합니다.

첫 번째 줄에는 암호 메시지의 개수가 주어집니다.

각 암호 메시지마다 먼저 한 줄에 메시지를 이루는 문자 수(최대 $200$)가 주어지고, 그다음 줄에 암호 메시지가 주어집니다. 메시지의 각 문자는 위에서 설명한 바퀴의 42개 문자 중 하나입니다.

각 암호 메시지에 대해, 먼저 메시지 번호를 Melding i 형식으로 한 줄에 출력합니다($i$는 $1$부터 시작).

가능한 복호화마다 Alternativ k: 뒤에 곧바로(콜론 뒤 공백 없이) 복호화된 텍스트를 붙여 한 줄씩 출력합니다($k$는 $1$부터 시작). 여러 복호화가 있으면 안쪽 바퀴 위치(회전량)가 작은 것부터 큰 순서로 모두 출력합니다.

어떤 방법으로도 그 메시지를 복호화해 RØLP가 나오게 할 수 없으면 Ingen dekodinger를 출력합니다.

Melding, Alternativ, Ingen dekodinger는 언어와 무관하게 그대로 출력해야 하는 고정된 문자열입니다.