Romeo and Tulio are two Roman thugs that through the power of plot-devices and time-travel have found their way to CS 1.24. On their way to programming greatness, they are having a spat about how to write numbers in this new-fangled Arabic numerals everyone seems to be using nowadays.

Specifically, they have \(n\) numbers they want to translate from our well understood base-10 Arabic numerals to roman numerals. Can you help them write a program to do so?

Romeo and Tulio weren't too good with numbers, to begin with, so they can only count from 1 to 9999 (or I to MXCMXCIX). For reference here are the basic Roman numerals you will need to know.

I - 1
V - 5
X - 10
L - 50
C - 100
D - 500
M - 1000

And some common combinations to get your thinking started.

III - 3
IV - 4
IX - 9
XL - 40

Input Specification

The first line will contain a single integer \(n (1 \leq n \leq 9999)\), the number of test cases to follow.

Each of the \(n\) lines following will contain a single number \(x (1 \leq x \leq 9999)\)

Output Specification

For each of the \(n\) test-cases output a single line containing the Roman numeral representation for \(x\), the input number.

Sample Input 1

3
1
12
7

Sample Output 1

I
XII
VII

Sample Input 2

3
101
99
432

Sample Output 2

CI
XCIX
CDXXXII

Note

This problem, while not computationally intensive, has a number of possible solutions of varying complexity, robustness and relevance to computer science generally. Consider how you might make your implementation more generic? Support larger numbers, different number systems entirely or implementation in other languages?

We strongly encourage discussion online with others.