A to Z 수 체계

로마 숫자는 기호 I, V, X, L, C, D, M을 사용하며 각각 $1, 5, 10, 50, 100, 500, 1000$을 나타낸다. 하나의 로마 숫자는 다음 규칙 하나로 값을 계산한다.

• 규칙 Δ. 어떤 기호가 맨 오른쪽에 있거나, 바로 오른쪽 기호의 값이 자기 값보다 크지 않으면 그 기호는 더한다. 그렇지 않으면 뺀다.

예: MMCDLXIX $= 1000 + 1000 - 100 + 500 + 50 + 10 - 1 + 10 = 2469$.

양의 정수에 대응하는 숫자를 유일하게 정하기 위해, 다음 규칙을 우선순위 순서대로 적용한다.

1. 기호를 최대한 적게 사용한다 (IIII가 아니라 IV).
2. 더해지는 기호들을 왼쪽에서 오른쪽으로 읽으면 감소하지 않는 부분수열을 이룬다 (VIX가 아니라 XIV).
3. 가장 짧은 숫자들 중에서는 빼는 기호의 개수가 가장 적은 것을 사용한다.
4. 그래도 동점이면, 빼는 기호를 최대한 오른쪽에 놓는다.

이 규칙들은 고전적인 로마 숫자 제한보다 느슨하므로, 규칙 Δ만 지키면 더 짧은 표기가 허용된다: IM $= -1 + 1000 = 999$, ICIC $= -1 + 100 - 1 + 100 = 198$, IVC $= -1 - 5 + 100 = 94$. 예를 들어 $297$은 CCVCII와 ICICIC 모두 올바르게 계산되지만, 규칙 3에 따라 빼는 기호가 더 적은 CCVCII를 택한다.

이제 로마 기호 대신 더 규칙적이고 확장 가능한 문자 집합을 쓴다. 문자 a, A, b, B, c, C, …, z, Z는 각각 $1, 5, 10, 5\cdot10, 10^{2}, 5\cdot10^{2}, \dots, 10^{25}, 5\cdot10^{25}$을 나타낸다. 즉 위치 $i$($0$부터 시작)의 소문자는 $10^{i}$, 짝이 되는 대문자는 $5\cdot10^{i}$이다. 이 문제에서는 a–r와 A–R만 사용하므로 가장 큰 기호는 r $= 10^{17}$, R $= 5\cdot10^{17}$이다.

형성 규칙 1–4와 규칙 Δ를 이 문자 집합에 적용한 것을 A to Z 수라고 한다. 예: ad $= -1 + 1000 = 999$, aAc $= -1 - 5 + 100 = 94$. 하나의 숫자 안에서 같은 대문자는 두 번 이상 나올 수 없다.

입력은 각각 $7\cdot10^{17}$ 미만인 하나 이상의 양의 정수로 이루어지며, 한 줄에 하나씩 주어진다. 마지막 줄에는 0만 주어지며 입력의 끝을 나타낸다.

각 양의 정수에 대해, 그 수를 나타내는 A to Z 수를 한 줄에 하나씩 출력한다. 자릿수에 대해 지수 시간이 걸리는 방법은 사용하지 마라.