7499번 - Hexaroman Numbers 다국어

Roman numerals are numeral system of ancient Rome based on letters of the alphabet, which are combined to signify the sum (or in some cases, the difference) of their values. This system is decimal but not directly positional, since same digits standing at different positions in usual decimal system are represented by different Roman digits, and one decimal digit could be represented by few Roman.

There are seven Roman numerals associated to the decimal I = 1, V = 5, X = 10₁₀, L = 50₁₀, C = 100₁₀, D = 500₁₀, M = 1000₁₀. Generally, Roman numerals are written in descending order from left to right, and are added sequentially, for example MMX (2010) is interpreted as 1000 + 1000 + 10. Certain combinations employ a subtractive principle, which specifies that where a symbol of smaller value precedes a symbol of larger value, the smaller value is subtracted from the larger value, and the result is added to the total. For example, MCMXLIV equals 1944. I may precede V and X, X may precede L or C. The numerals V, L, and D may not be followed by a numeral of greater or equal value.

Subtractive principle has been introduced at medevail adges. Originally it allowes only one symbol of smaller value to preced a symbol of larger value. Nowadays this limitation could be skipped to allow shorter notation for some numbers. Also modern computers are much better in hexadecimal numbers and probably it makes sence to introduce "hexadedimal" Roman notation.

Let hexadecimal Roman notation be a notation in which Roman numerals are equivalent to the following numbers: I = 1, V = 8, X = 10₁₆, L = 80₁₆, C= 100₁₆, D = 800₁₆, M = 1000₁₆. Is some hexadecima digit can be represented using addition and subtraction, notation with less symbols is used. If both notations produce same number of symbols addition is used. For example number F₁₆ is written as IX₁₆, 5C8₁₆ becomes CCCDLXXXXV₁₆.

You need to write a program which can perform computation in hexadecimal Roman notation, namely the following operations: addition, subtraction, and multiplication. All source numbers and results will be integers within [1, 4FFF₁₆].

The first line at input contains one integer N (0 < N ≤ 100), the number of test lines. Each line contains test data in format "<A><O><B>" whitout any spaces. <A> and <B> are numbers in hexadecimal Roman notation, <O> designates operation: +, -, *.

Every line at output should contain hexadecimal Roman notation of calculation result for corresponding test line at the input.