A to Z Numerals

Roman numerals use symbols I, V, X, L, C, D, and M with values 1, 5, 10, 50, 100, 500, and 1000 respectively. There is an easy evaluation rule for them:

Rule $\Delta $:

Add together the values for each symbol that is either the rightmost or has a symbol of no greater value directly to its right. Subtract the values of all the other symbols.

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

Further rules are needed to uniquely specify a Roman numeral corresponding to a positive integer less than 4000:

1. The numeral has as few characters as possible. (IV not IIII)

2. All the symbols that make positive contributions form a non-increasing subsequence. (XIV, not VIX)

3. All subtracted symbols appear as far to the right as possible. (MMCDLXIX, not MCMDLIXX)

4. Subtracted symbols are always for a power of 10, and always appear directly to the left of a symbol 5 or 10 times as large that is added. No subtracted symbol can appear more than once in a numeral.

Rule 4 can be removed to allow shorter numerals while still using the same evaluation rule. For example: IM = $-1 + 1000 = 999$, ICIC = $-1 + 100 + -1 + 100 = 198$, IVC = $-1 -5 + 100 = 94$.

This would not make the numerals unique, however. Two choices for 297 would be CCVCII and ICICIC. To eliminate the second choice, Rule 4 can be replaced by:

Rule 4’. With a choice of numeral representations of the same length, use one with the fewest subtracted symbols.

Finally, replace the Roman numeral symbols with a more regular system that allows larger numbers. Assign the English letters a, A, b, B, …, z, Z to values:

Though using the full alphabet makes logical sense, this problem only uses symbols from a to R, where R = $(5)10^{17}$.

With the new symbols a-Z, and the same formation rules (1–3), the alternate Rule 4’, and the evaluation rule $\Delta $, numerals can be created—called A to Z numerals. Examples: ad = $-1 + 1000 = 999$, aAc = $-1 - 5 + 100 = 94$.

Note: For this problem, an A to Z Numeral cannot include the same uppercase literal more than once.

Input

The input starts with a sequence of one or more positive integers less than $ 7 \times 10^{17} $, one per line. The end of the input is indicated by a line containing only 0.

Output

For each positive integer in the input, output a line containing only an A to Z numeral representing the integer.

Do not choose a solution method whose time is exponential in the number of digits!

999
0

ad

198
0

acac

98
0

Acaaa

297
0

ccAcaa

94
0

aAc

666666666666666666
0

RrQqPpOoNnMmLlKkJjIiHhGgFfEeDdCcBbAa