Шестнадцатиричные римские числа
Рассмотрим традиционную "римскую" систему счисления и построим её обобщение.
В обычной ("десятичной") римской записи используют 7 римских цифр: I = 1, V = 5, X = 10_10, L = 50_10, C = 100_10, D = 500_10, M = 1000_10.
Обычно римские цифры записывают в убывающем порядке и при этом значения цифр складываются (например, MMX (2010) интерпретируется как 1000 + 1000 + 10). Если цифра с меньшим значением идёт перед цифрой с большим значением, меньшее значение вычитается из большего и прибавляется к общей сумме. Например, MCMXLIV равно 1944. На конструкции с вычитание существуют следующие ограничения: I может идти только перед V и X, X может идти только перед L или C. За цифрами V, L и D могут идти только цифры с большим значением.
Введём шестнадцатиричную римскую запись по следующим правилам: цифрам присваиваются значения I = 1, V = 8, X = 10_16, L = 80_16, C = 100_16, D = 800_16, M = 1000_16.
Ограничения на использование цифр такие же, как в "десятичной" римской системе, за исключением того, что запись типа IIX является корректной. Если какое-то число из-за этого может быть представлено разными способами, используется запись с меньшим количеством знаков, если количество знаков одинаково, то используется запись с меньшим количеством вычитаний (например, из записей IIIIX и VIIII для числа C_16 выбирается вторая). Например, число F_16 записывается как IX_16, а 5C8_16 - как CCCDLXXXXV_16.
Напишите программу, которая производит операции над шестнадцатиричными римскими числами (сложение, вычитание, умножение). Гарантируется, что входные данные и результаты вычислений - целые положителтьые числа, не превышающие 4FFF_16.
Входные данные
В первой строке входного файла задано целое число N (0 < N ≤ 100) - количество тестовых случаев. Каждый тестовый пример содержит задание в формате <A><O><B>. <A> и <B> - числа в шестнадцатиричной римской записи, <O> - одна из операций: +, -, *. Ни один текстовый пример не содержит пробелов.
Выходные данные
Для каждого примера выведите в отдельной строке результат вычислений, представленный в шестнадцатиричной римской записи.