Problem F
Converting Romans
The Roman numerals are a numeral system that originated in ancient Rome and was widely used throughout Europe well into the Late Middle Ages. It differs from the Arabic system that we mostly use today in that numbers are written with combinations of letters from the Latin alphabet, where each letter is assigned a fixed integer value. Over the years many different letters were used, which was a cause of frequent confusion. But “modern” style uses only these seven:
|
I |
V |
X |
L |
C |
D |
M |
|
1 |
5 |
10 |
50 |
100 |
500 |
1000 |
A very common misunderstanding of the Roman numerals is that they use a universal subtractive syntax. In a subtractive syntax, a lower digit written before a larger digit will be subtracted from the larger digit. 4 can be written as IIII and IV $(5-1)$. Romans themselves only really used the subtractive syntax for smaller numbers. For larger numbers, it was largely avoided, to give more clarity. For example, $499$ can be written LDVLIV, XDIX, VDIV or ID, while older sources most likely would use CDXCIX. Ain’t Roman numbers fun?
You are given $n$ numbers written in the Roman numeral system, and your task is to convert them to the regular Arabic number system.
For the purposes of this problem we will subtract any digit written to the left of a larger digit, even if they are not directly adjacent.
Input
The inputs starts with an integer $0 < n \leq 10^3$. Then follow $n$ lines, each containing up to $3 \cdot 10^5$ Roman digits. The total number of Roman digits in the input is at most $3 \cdot 10^5$.
Output
Output the corresponding Arabic numbers, one number per line.
| Sample Input 1 | Sample Output 1 |
|---|---|
5 CDXCIX ID IV IIIIV IIIIIIV |
499 499 4 1 -1 |
