헥사로만 수

로마 숫자(Roman numeral)는 알파벳 문자를 조합하여 값의 합(경우에 따라 차)을 나타내는 고대 로마의 기수법이다. 이 체계는 십진법이지만 자리값이 직접적으로 위치로 정해지지는 않는다. 일반적인 십진법에서 같은 숫자가 서로 다른 자리에 오면 로마 숫자에서는 서로 다른 기호로 표현되고, 하나의 십진 숫자가 여러 개의 로마 기호로 표현되기도 한다.

일곱 개의 로마 기호는 각각 다음 십진수에 대응한다: $I = 1$, $V = 5$, $X = 10$, $L = 50$, $C = 100$, $D = 500$, $M = 1000$. 로마 숫자는 보통 왼쪽에서 오른쪽으로 값이 큰 순서대로 쓰며 차례로 더한다. 예를 들어 $MMX$는 $1000 + 1000 + 10 = 2010$으로 해석된다. 어떤 조합은 뺄셈 원리를 사용하는데, 값이 작은 기호가 값이 큰 기호 앞에 오면 작은 값을 큰 값에서 빼고 그 결과를 합에 더한다. 예를 들어 $MCMXLIV = 1944$이다. $I$는 $V$나 $X$ 앞에, $X$는 $L$이나 $C$ 앞에 올 수 있다. $V$, $L$, $D$ 뒤에는 그와 같거나 더 큰 값의 기호가 올 수 없다.

뺄셈 원리는 중세에 도입되었다. 원래는 값이 작은 기호 하나만 값이 큰 기호 앞에 올 수 있었다. 오늘날에는 이 제한을 없애 일부 수를 더 짧게 표기할 수 있다. 또한 현대 컴퓨터는 16진수를 훨씬 자연스럽게 다루므로, "16진" 로마 표기법을 도입하는 것도 의미가 있다.

16진 로마 표기법에서 로마 기호는 다음 값에 대응한다: $I = 1$, $V = 8$, $X = 16$, $L = 128$, $C = 256$, $D = 2048$, $M = 4096$ (즉 16진수로 각각 $1$, $8$, $10$, $80$, $100$, $800$, $1000$). 각 16진 자리 숫자는 기호 수가 더 적은 표기(덧셈 또는 뺄셈)를 사용한다. 두 표기의 기호 수가 같으면 덧셈 표기를 사용한다. 예를 들어 16진수 $F$는 $IX$로 쓰고, 16진수 $5C8$은 $CCCDLXXXXV$가 된다.

16진 로마 표기법으로 덧셈, 뺄셈, 곱셈을 수행하는 프로그램을 작성하라. 모든 입력 수와 결과는 16진수로 $1$ 이상 $4FFF$ 이하의 정수이다.

입력의 첫 번째 줄에는 검사할 줄의 개수 $N$ ($0 < N \le 100$)이 주어진다. 이어지는 각 줄에는 공백 없이 <A><O><B> 형식의 데이터가 주어진다. <A>와 <B>는 16진 로마 표기법으로 쓰인 수이고, <O>는 연산 기호로 +, -, * 중 하나이다.

각 입력 줄에 대해 계산 결과를 16진 로마 표기법으로 한 줄에 하나씩 출력한다.