A to Z Numerals

Roman numerals use the symbols I, V, X, L, C, D, M, worth $1, 5, 10, 50, 100, 500, 1000$. A written numeral is evaluated by one rule:

• Rule Δ. A symbol is added when it is the last symbol, or when the symbol directly to its right is worth no more than it is. Otherwise the symbol is subtracted.

For example, MMCDLXIX $= 1000 + 1000 - 100 + 500 + 50 + 10 - 1 + 10 = 2469$.

To make the numeral for a positive integer unique, the following rules are applied in order of priority:

1. Use as few symbols as possible (IV, not IIII).
2. The added symbols, read from left to right, form a non-increasing subsequence (XIV, not VIX).
3. Among the shortest numerals, use one with the fewest subtracted symbols.
4. If a tie still remains, the subtracted symbols are placed as far to the right as possible.

These rules are weaker than the classical Roman restriction, so shorter forms are allowed as long as rule Δ still holds: IM $= -1 + 1000 = 999$, ICIC $= -1 + 100 - 1 + 100 = 198$, IVC $= -1 - 5 + 100 = 94$. For $297$ both CCVCII and ICICIC evaluate correctly, but rule 3 keeps CCVCII, which subtracts fewer symbols.

Now use a more regular, extensible alphabet in place of the Roman symbols. The letters a, A, b, B, c, C, …, z, Z stand for $1, 5, 10, 5\cdot10, 10^{2}, 5\cdot10^{2}, \dots, 10^{25}, 5\cdot10^{25}$; that is, the lowercase letter at position $i$ (counting from $0$) is $10^{i}$ and its uppercase partner is $5\cdot10^{i}$. This problem uses only a–r and A–R, so the largest symbols are r $= 10^{17}$ and R $= 5\cdot10^{17}$.

Applying formation rules 1–4 together with rule Δ to this alphabet yields A to Z numerals. For example ad $= -1 + 1000 = 999$ and aAc $= -1 - 5 + 100 = 94$. The same uppercase letter may not appear more than once in a numeral.

The input contains one or more positive integers, each less than $7\cdot10^{17}$, one per line. The list ends with a line containing only 0.

For each positive integer, print its A to Z numeral on its own line. Do not use a method whose running time is exponential in the number of digits.