Шістнадцяткові римські числа
Розглянемо традиційну "римську" систему числення і побудуємо її узагальнення.
У звичайному ("десятковому") римському запису використовують 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> - одна з операцій: +, -, *. Жоден текстовий приклад не містить пропусків.
Вихідні дані
Для кожного прикладу виведіть у окремому рядку результат обчислень, поданий у шістнадцятковому римському запису.