쿠르트 괴델

쿠르트 프리드리히 괴델은 오스트리아의 수학자이자 철학자다. 아이작 뉴턴과 이마누엘 칸트 같은 앞선 과학자, 철학자에게서 영향을 받았고, 나중에는 버트런드 러셀 같은 수학자와 철학자에게 영향을 주었다. 괴델은 수학과 논리 자체의 경계를 시험한 불완전성 정리를 증명하면서 괴델 수 부호화를 썼다. 그래서 괴델을 아리스토텔레스와 함께 논리학 역사에서 가장 중요한 인물로 꼽는다.

괴델 수 부호화가 어떻게 동작하는지 보자. 먼저 기호마다 번호를 붙인다. 이 문제에서 기호는 알파벳 대문자 A부터 Z까지이고, 차례대로 자연수 1부터 26까지에 대응시킨다. A는 1, B는 2에 대응하고, 마지막 Z는 26에 대응한다. 그러면 KURT라는 단어는 수열 (11, 21, 18, 20)이 된다. 다음으로 이 수열을 소수의 거듭제곱의 곱으로 나타낸다. 수열 $(a_1, a_2, \dots, a_n)$은 $2^{a_1} \times 3^{a_2} \times \cdots \times p_n^{a_n}$으로 부호화하며, $p_i$는 $i$번째 소수다. 따라서 KURT의 괴델 수는 $2^{11} \times 3^{21} \times 5^{18} \times 7^{20} = 6520744440162926921184290648437500000000000$이다.

긴 단어의 괴델 수는 아주 크다. 친구 알베르트는 괴델 수로 메시지를 남기고 싶지만, 자릿수를 다 적기는 귀찮아한다. 그래서 괴델 수 $g$를 세 수 $(\ell, r, p)$로 줄여 적는다. $\ell$은 원래 단어의 길이, $p$는 소수, $r$은 $g$를 $p$로 나눈 나머지다. 그런데 알베르트는 서로 다른 두 단어가 같은 세 수를 만든다는 사실을 놓쳤다. 예를 들어 EA와 JA의 괴델 수는 각각 96과 3072지만, 알베르트는 둘 다 $(2, 3, 31)$로 적을 수 있다. 알베르트의 메시지를 해독해 보자.

테스트 케이스는 최대 30개다. 각 테스트 케이스는 정수 세 개가 공백으로 구분되어 한 줄에 주어진다. 첫 번째 정수 $\ell$ $(1 \le \ell \le 8)$은 단어의 길이다. 두 번째 정수 $r$은 괴델 수를 $p$로 나눈 나머지다. 세 번째 정수 $p$는 나머지 연산에 쓴 소수다. 항상 $0 \le r < p < 2^{31}$이다. 입력은 0 세 개가 적힌 줄로 끝나며, 그 줄은 테스트 케이스가 아니다. 단어는 알파벳 대문자 A부터 Z까지로만 이루어진다.

각 테스트 케이스마다 한 줄을 출력한다. 길이가 $\ell$이고 주어진 세 수를 만드는 단어가 정확히 하나면 그 단어를 출력한다. 그런 단어가 둘 이상이면 ambiguous를 출력한다. 그런 단어가 하나도 없으면 not a word를 출력한다.