B. Roman Empire
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

After Roman Reigns' historic 1316-day title reign came to an end at WrestleMania 40, his cousin Dwayne "The Rock" Johnson decided to write a 1316-page book chronicling the reign.

To make it iconic, he wants to number each page using Roman numerals. Unfortunately, The Final Boss is not very good at counting.

You need to help him convert the page numbers from standard representation to Roman numerals.

Roman numerals are a number system that uses letters from the Latin alphabet to represent values. The basic symbols and their corresponding values are:

$$$\mathtt{I} = 1,\quad \mathtt{V} = 5,\quad \mathtt{X} = 10,\quad \mathtt{L} = 50,\quad \mathtt{C} = 100,\quad \mathtt{D} = 500,\quad \mathtt{M} = 1000$$$

Roman numerals are usually written from largest to smallest. When this rule is followed strictly, the numeral is evaluated as a sum of its parts. This is called additive notation. For example: $$$1316 = 1000 + 100 + 100 + 100 + 10 + 5 + 1 = \texttt{MCCCXVI}$$$.

However, to avoid repeating the same symbol four or more times in a row, Roman numerals also allow a smaller value to appear before a larger one. In such cases, the smaller value is subtracted from the larger. This is called subtractive notation. Examples: $$$\texttt{IV} = 5 - 1 = 4$$$, $$$\texttt{IX} = 10 - 1 = 9$$$, $$$\texttt{XL} = 50 - 10 = 40$$$, $$$\texttt{XC} = 100 - 10 = 90$$$, $$$\texttt{CD} = 500 - 100 = 400$$$, $$$\texttt{CM} = 1000 - 100 = 900$$$.

Using both additive and subtractive notation, the number $$$1248$$$ can be expressed as MCCXLVIII.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 1316$$$) — the number of test cases.

Each test case consists of a single line containing a single integer $$$n$$$ ($$$1 \le n \le 1316$$$) — the standard representation of the page number that needs to be converted.

Output

For each test case, output one string in a line — the Roman numeral representation of $$$n$$$.

Example
Input
8
3
12
17
19
49
999
1248
1316
Output
III
XII
XVII
XIX
XLIX
CMXCIX
MCCXLVIII
MCCCXVI