Hexaroman Numbers

Time limit1sMemory limit128 MB

Summary

Parse and output hexadecimal Roman numerals, choosing the shorter of additive or subtractive notation per digit, then evaluate +, -, and * expressions.

Level: Medium7 of 10
Topics: String, Implementation, Math, Simulation
Solved: No attempts yet

Problem

Roman numerals are the numeral system of ancient Rome, based on letters of the alphabet that are combined to signify the sum (or in some cases the difference) of their values. The system is decimal but not directly positional: the same digit in different positions of the usual decimal system is represented by different Roman symbols, and a single decimal digit may be represented by several Roman symbols.

The seven Roman symbols correspond to the decimal values $I = 1$ , $V = 5$ , $X = 10$ , $L = 50$ , $C = 100$ , $D = 500$ , $M = 1000$ . Roman numerals are generally written from left to right in descending order and added in sequence; for example $MMX$ is interpreted as $1000 + 1000 + 10 = 2010$ . Certain combinations use the subtractive principle: when a symbol of smaller value precedes a symbol of larger value, the smaller value is subtracted from the larger one and the result is added to the total. For example $MCMXLIV = 1944$ . $I$ may precede $V$ or $X$ , and $X$ may precede $L$ or $C$ . The symbols $V$ , $L$ , and $D$ may not be followed by a symbol of greater or equal value.

The subtractive principle was introduced in the Middle Ages. Originally it allowed only a single smaller symbol to precede a larger one. Today this restriction can be dropped to allow shorter notation for some numbers. Because modern computers work much more naturally with hexadecimal numbers, it also makes sense to introduce a "hexadecimal" Roman notation.

Let hexadecimal Roman notation be a notation in which the Roman symbols correspond to the following values: $I = 1$ , $V = 8$ , $X = 16$ , $L = 128$ , $C = 256$ , $D = 2048$ , $M = 4096$ (that is, $1$ , $8$ , $10$ , $80$ , $100$ , $800$ , $1000$ in hexadecimal). For each hexadecimal digit, the notation with fewer symbols (using addition or subtraction) is used. If both notations use the same number of symbols, the additive notation is used. For example, the hexadecimal number $F$ is written as $IX$ , and $5C8$ becomes $CCCDLXXXXV$ .

You must write a program that performs computation in hexadecimal Roman notation, namely addition, subtraction, and multiplication. Every input number and every result is an integer between $1$ and $4FFF$ (hexadecimal), inclusive.

Input

The first line contains one integer $N$ ( $0 < N \le 100$ ), the number of test lines. Each of the following lines contains data in the format <A><O><B> with no spaces. <A> and <B> are numbers in hexadecimal Roman notation, and <O> denotes the operation, one of +, -, or *.

Output

For each input line, output the hexadecimal Roman notation of the corresponding result on its own line.

Examples4

Example 1

Input

3
XIIV+XXXXII
XXIIII*XXXIII
XXIV*IV

Expected output

XXXLV
CDXXVIIII
CXI

Example 2
Input
```
1
I+I
```
Expected output
```
II
```
Example 3
Input
```
1
II-I
```
Expected output
```
I
```
Example 4
Input
```
1
IV+V
```
Expected output
```
IX
```