ROMAN - Converting number formats

no tags 

Given the number n of test cases, convert n positive integers less than 2^32 (given one per line) from one representation to another. For convenience, n is given in the same format as the other numbers.

Input

Input is given by spelling the number in english digits (all upper case letters). Thus the range of (32-bit) input values permissible extends from ZERO (or OH) through FOUR TWO NINE FOUR NINE SIX SEVEN TWO NINE FIVE.

Output

Output 2 lines for each test case. Output is in the form of "extended" Roman numerals (also called "butchered" Roman numerals), with an overline (see sample for details) indicating the value below is "times 1000", and lower-case letters indicating "times 1000000". Thus, the range of (32-bit) output values possible is from through ivccxcivCMLXVIICCXCV, where there is a line above iv and CMLXVII. Note: For values whose residues modulo 1000000 are less than 4000, M is used to represent 1000; for values whose residues are 4000 or greater, I is used. Thus 3999 would read out as MMMCMXCIX while 4000 would readout as IV with an overline. Similar rules apply to the use of M and i for 1000000, and to that of m and i for 1000000000.

WARNING: This problem has a somewhat strict source limit

Example

Input:
THREE
FOUR OH
ONE NINE NINE NINE NINE NINE NINE NINE NINE NINE
ONE TWO THREE ZERO FOUR FIVE

Output:
  
XL
       ______      
mcmxcixCMXCIXCMXCIX
___      
CXXMMMXLV

hide comments
Jacob Plachta: 2013-03-07 06:34:24

In determining whether to use M or I, the problem states that you should mod by 1000000 and compare to 4000. This is incorrect - you should instead mod by 10000. Same goes for the higher powers.


Added by:overwise
Date:2004-11-30
Time limit:1.052s
Source limit:2048B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All