Integer to Roman Numeral Conversion

You are given a list of positive integers. For each integer, convert it to its corresponding Roman numeral representation.

The Roman numeral system uses the following symbols:

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

Additionally, subtractive notation is used, e.g. IV for 4, IX for 9, XL for 40, XC for 90, CD for 400, and CM for 900. In mathematical notation, the conversion can be formulated as follows:

Given an integer \( n \) where \( 1 \leq n \leq 3999 \), decompose it with the values \( \{1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1\} \) and corresponding symbols \( \{M, CM, D, CD, C, XC, L, XL, X, IX, V, IV, I\} \).

Your task is to read a list of integers from standard input and print the Roman numeral representation for each integer on a new line.

inputFormat

The first line of input contains an integer T denoting the number of test cases. Each of the following T lines contains one integer n (where \(1 \leq n \leq 3999\)).

For example:

3
3
58
1994

outputFormat

For each test case, output the Roman numeral representation of the given integer on a separate line.

For example, the output for the sample input above is:

III
LVIII
MCMXCIV

## sample

3
3
58
1994

III
LVIII
MCMXCIV

</p>