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:
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.
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.
For each test case, output one string in a line — the Roman numeral representation of $$$n$$$.
831217194999912481316
III XII XVII XIX XLIX CMXCIX MCCXLVIII MCCCXVI
