ARABICNUM - Arabic Numbers

no tags 

Roman does not like the Roman numbering system. That is why he has asked you to write a program that quickly converts Roman numbers to the modern Arabic (decimal) numbers which are used everywhere nowadays.

To help you write the program, Roman has provided you with the necessary information for comprehending Roman numbers.

Roman numbers have 7 basic letters and their corresponding Arabic number equivalents are as follows: I=1, V=5, X=10, L=50, C=100, D=500, M=1000

Roman Numerals also have the following letter pairs: IV=4, IX=9, XL=40, XC=90, CD=400, CM=900

Generally numerals are joined together to give their overall value. Although the Romans used a different system to represent large numbers (e.g. 4000 and beyond), for this problem it is assumed that M can be consecutively repeated as many times as needed to represent large numbers. All other letters can be consecutively repeated thrice at most. Observe the sample outputs to get a better understanding.

Roman has promised to take you on a trip to Rome if you write this program for him. You love travelling, so you decide to write a program for Roman that will convert Roman numbers to their equivalent Arabic numbers.

Input

Input begins with a line containing a single integer T (1 <= T <= 10000), denoting the number of test cases. T test cases follow. Each test case consists of a single line containing a Roman number. None of these numbers will have value exceeding 10000 and all of these numbers are valid under the rules stated in the problem statement.

Output

For each test case, output a single line in the format Case X: Y, where X denotes the test case number and Y denotes the equivalent Arabic number obtained following the rules stated in the problem statement.

Example

Input:
3
MCDLIII
MCMLXXIX
MMMMM

Output:
Case 1: 1453
Case 2: 1979
Case 3: 5000


Added by:imranziad
Date:2015-11-25
Time limit:0.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:AIUB CS Fest 2015 (H.M. Mehrab)