14472 - Roman to Integer   

Status  |  Limits Submit

Description

Mr. Tim was assigned to gather data about the number of elephants in each country. However the data numbers are shown using Roman Symbols, your task is to translate the Roman number into an integer

 

Roman numbers are represented by symbols I, V, X, L, C, D, and M, and below is the table of each symbol value

Symbol Value
I 1
V 5
X 10
L 50
C 100
D 500
M 1000

Here is the rule of legal roman:

  1. Symbol can be repeated to representing some value I, X, and C, and M can be repeated, for a maximum of 3 times, example:
    III representing 3 (1+1+1 = 3)
    XX representing 20
    CCCC is illegal (more than 3 consecutive symbols)
    VV is illegal (only I, X, C, and M is allowed)
  2. Some combinations can represent subtractive notation, the full list is:
    IV representing 4 (5-1)
    IX representing 9 (10-1)
    XL representing 40 (50-40)
    XC representing 90 (100-10)
    CD representing 400 (500-100)
    CM representing 900 (1000-100)
    Other subtractive notation combinations (e.g. IC) are illegal
  3. The roman must be in descending order (Biggest to Lowest) to make a combination for example:
    XXVII representing 27 (10+10+5+1+1)
    Subtractive notation can be also put as long as it's in order, for example:
    XIV representing 14 (10 + (5 - 1))
    MXCI representing 1091 (1000 + (100 - 10) + 1)
    XXXIX is legal, representing 39 (10 + 10 + 10 + 9)
    MIC is illegal as it's not in descending order and the symbol IC is not included in rule number 2
    MDD is illegal as it violate rule number 1
    XXL is illegal as XL > X and L > XX, no correct combination here
    XLXL is illegal (the correct way to represent 80 is LXXX, the same subtractive notation can't be consecutive)
    IXI is illegal (there is a more simple way to represent 10, which is X)

Your task is to determine if the number is legal or illegal, if it's legal try to convert the roman to integer representation

Input

There are T testcases

1 <= T <= 100
Each testcase will have only 1 string

Length of string will be <= 20

For testcase 1~3: no illegal format, no subtractive notation, guaranteed in descending order
For testcase 4~5: no illegal format, subtractive notation exist
For testcase 6: no further restriction

Output

For each testcase, please print the number in integer, following by newline character

If it's in illegal format, print "QQ" without the quotes

Sample Input  Download

Sample Output  Download

Tags




Discuss