Roman number is very useful number system. Often we need to convert a decimal number into Roman number. In Roman number the following symbol are used: I, V, X, L, C, D, M for 1, 5, 10, 50, 100, 500 and 1000 respectively.

Input

Quantity of decimal numbers to convert to Roman and each of the decimal system numbers.

Output

Roman number equivalent.

Example

Input:
4
15
245
455
690

Output:
XV
CCXLV
CDLV
DCXC

Input:
2
18
345

Output:
XVIII
CCCXLV

Input:
3
500
124
248

Output:
D
CXXIV
CCXLVIII