시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 21 18 13 86.667%

문제

로마인들은 알파벳의 일곱 문자를 통해서 수를 표현했다. 다음은 문자와 그에 대응하는 값을 보여주는 표이다.

  • I = 1
  • V = 5
  • X = 10
  • L = 50
  • C = 100
  • D = 500
  • M = 1000

이 7개의 숫자와 다음 규칙들을 통해서, 로마인들은 원하는 모든 수를 적을 수 있었다.

  • 만약에 주어지는 숫자들이 감소순으로 좌에서 우로 적혀있다면, 덧셈법칙을 쓸 수 있다. 예를 들어, 로마숫자 MMCLVII는 1000 + 1000 + 100 + 50 + 5 + 1 + 1 = 2157이다.
  • 이는 로마숫자를 지나치게 길게 하는 단점이 있어 뺄셈법칙 역시 존재한다. 만약에 왼쪽에 오른쪽에 있는 문자보다 작은 숫자가 적혀있다면, 왼쪽에 있는 수를 빼야한다. 예를 들어, 로마숫자 MCMXIV는 1000 − 100 + 1000 + 10 − 1 + 5 = 1914이다.
  • I, X, C를 네번 이상 연달아 쓸 수 없다. IIII는 IV와 같은 더 짧은 꼴로 바꿔야 한다.
  • V, L, D를 두번 이상 연달아 쓸 수 없다.
  • M에 대해서는 제한이 없다.
  • 뺄셈 법칙은 한개의 왼쪽 숫자에 대해서만 작동한다, 즉, IV는 4이지만, IIV는 3이 아니며 로마 숫자도 아니다.
  • 뺄셈 법칙에 붙을 수 있는 왼쪽 숫자는 I, X, C 뿐이다.
  • 뺄셈 법칙에서 I는 V / X 옆에만, X는 L / C 옆에만, C는 D / M 옆에만 올 수 있다.

이 규칙을 만족하는 로마숫자들이 주어질 때 이를 십진수 정수로 바꾸시오.

입력

첫 번째 줄에는 N이 주어진다. N은 변경할 로마 숫자의 수이다.

이후 N개의 줄에 로마숫자가 하나씩 주어진다. 로마숫자는 위에 적혀있는 규칙을 따르며 10000 이하의 자연수이다.

출력

주어지는 로마숫자를 10진수 정수로 바꾸어서 한 줄씩 출력하라.

예제 입력 1

3
IX
MMDCII
DXII

예제 출력 1

9
2602
512

힌트

Daft Punk - Veridis Quo

W3sicHJvYmxlbV9pZCI6IjQ1MzEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJWZXJkaXMgUXVvIiwiZGVzY3JpcHRpb24iOiI8cD5cdWI4NWNcdWI5YzhcdWM3NzhcdWI0ZTRcdWM3NDAgXHVjNTRjXHVkMzBjXHViY2IzXHVjNzU4IFx1Yzc3Y1x1YWNmMSBcdWJiMzhcdWM3OTBcdWI5N2MgXHVkMWI1XHVkNTc0XHVjMTFjIFx1YzIxOFx1Yjk3YyBcdWQ0NWNcdWQ2MDRcdWQ1ODhcdWIyZTQuIFx1YjJlNFx1Yzc0Y1x1Yzc0MCBcdWJiMzhcdWM3OTBcdWM2NDAgXHVhZGY4XHVjNWQwIFx1YjMwMFx1Yzc1MVx1ZDU1OFx1YjI5NCBcdWFjMTJcdWM3NDQgXHViY2Y0XHVjNWVjXHVjOGZjXHViMjk0IFx1ZDQ1Y1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5JID0gMTxcL2xpPlxyXG5cdDxsaT5WID0gNTxcL2xpPlxyXG5cdDxsaT5YID0gMTA8XC9saT5cclxuXHQ8bGk+TCA9IDUwPFwvbGk+XHJcblx0PGxpPkMgPSAxMDA8XC9saT5cclxuXHQ8bGk+RCA9IDUwMDxcL2xpPlxyXG5cdDxsaT5NID0gMTAwMDxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1Yzc3NCA3XHVhYzFjXHVjNzU4IFx1YzIyYlx1Yzc5MFx1YzY0MCBcdWIyZTRcdWM3NGMgXHVhZGRjXHVjZTU5XHViNGU0XHVjNzQ0IFx1ZDFiNVx1ZDU3NFx1YzExYywgXHViODVjXHViOWM4XHVjNzc4XHViNGU0XHVjNzQwIFx1YzZkMFx1ZDU1OFx1YjI5NCBcdWJhYThcdWI0ZTAgXHVjMjE4XHViOTdjIFx1YzgwMVx1Yzc0NCBcdWMyMTggXHVjNzg4XHVjNWM4XHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlx1YjljY1x1YzU3ZFx1YzVkMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWIyOTQgXHVjMjJiXHVjNzkwXHViNGU0XHVjNzc0IFx1YWMxMFx1YzE4Y1x1YzIxY1x1YzczY1x1Yjg1YyBcdWM4OGNcdWM1ZDBcdWMxMWMgXHVjNmIwXHViODVjIFx1YzgwMVx1ZDYwMFx1Yzc4OFx1YjJlNFx1YmE3NCwgXHViMzY3XHVjMTQ4XHViYzk1XHVjZTU5XHVjNzQ0IFx1YzRmOCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBcdWI4NWNcdWI5YzhcdWMyMmJcdWM3OTAgTU1DTFZJSVx1YjI5NCAxMDAwICsgMTAwMCArIDEwMCArIDUwICsgNSArIDEgKyAxID0gMjE1N1x1Yzc3NFx1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVjNzc0XHViMjk0IFx1Yjg1Y1x1YjljOFx1YzIyYlx1Yzc5MFx1Yjk3YyBcdWM5YzBcdWIwOThcdWNlNThcdWFjOGMgXHVhZTM4XHVhYzhjIFx1ZDU1OFx1YjI5NCBcdWIyZThcdWM4MTBcdWM3NzQgXHVjNzg4XHVjNWI0IFx1YmU4NFx1YzE0OFx1YmM5NVx1Y2U1OSBcdWM1ZWRcdWMyZGMgXHVjODc0XHVjN2FjXHVkNTVjXHViMmU0LiBcdWI5Y2NcdWM1N2RcdWM1ZDAgXHVjNjdjXHVjYWJkXHVjNWQwIFx1YzYyNFx1Yjk3OFx1Y2FiZFx1YzVkMCBcdWM3ODhcdWIyOTQgXHViYjM4XHVjNzkwXHViY2Y0XHViMmU0IFx1Yzc5MVx1Yzc0MCBcdWMyMmJcdWM3OTBcdWFjMDAgXHVjODAxXHVkNjAwXHVjNzg4XHViMmU0XHViYTc0LCBcdWM2N2NcdWNhYmRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YzIxOFx1Yjk3YyBcdWJlN2NcdWM1N2NcdWQ1NWNcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIFx1Yjg1Y1x1YjljOFx1YzIyYlx1Yzc5MCBNQ01YSVZcdWIyOTQgMTAwMCAmbWludXM7IDEwMCArIDEwMDAgKyAxMCAmbWludXM7IDEgKyA1ID0gMTkxNFx1Yzc3NFx1YjJlNC48XC9saT5cclxuXHQ8bGk+SSwgWCwgQ1x1Yjk3YyBcdWIxMjRcdWJjODggXHVjNzc0XHVjMGMxIFx1YzVmMFx1YjJlY1x1YzU0NCBcdWM0ZjggXHVjMjE4IFx1YzVjNlx1YjJlNC4gSUlJSVx1YjI5NCBJVlx1YzY0MCBcdWFjMTlcdWM3NDAgXHViMzU0IFx1YzllN1x1Yzc0MCBcdWFmMzRcdWI4NWMgXHViYzE0XHVhZmQ0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9saT5cclxuXHQ8bGk+ViwgTCwgRFx1Yjk3YyBcdWI0NTBcdWJjODggXHVjNzc0XHVjMGMxIFx1YzVmMFx1YjJlY1x1YzU0NCBcdWM0ZjggXHVjMjE4IFx1YzVjNlx1YjJlNC48XC9saT5cclxuXHQ8bGk+TVx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWNcdWIyOTQgXHVjODFjXHVkNTVjXHVjNzc0IFx1YzVjNlx1YjJlNC48XC9saT5cclxuXHQ8bGk+XHViZTg0XHVjMTQ4IFx1YmM5NVx1Y2U1OVx1Yzc0MCBcdWQ1NWNcdWFjMWNcdWM3NTggXHVjNjdjXHVjYWJkIFx1YzIyYlx1Yzc5MFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWNcdWI5Y2MgXHVjNzkxXHViM2Q5XHVkNTVjXHViMmU0LCBcdWM5ODksIElWXHViMjk0IDRcdWM3NzRcdWM5YzBcdWI5Y2MsIElJVlx1YjI5NCAzXHVjNzc0IFx1YzU0NFx1YjJjOFx1YmE3MCBcdWI4NWNcdWI5YzggXHVjMjJiXHVjNzkwXHViM2M0IFx1YzU0NFx1YjJjOFx1YjJlNC48XC9saT5cclxuXHQ8bGk+XHViZTg0XHVjMTQ4IFx1YmM5NVx1Y2U1OVx1YzVkMCBcdWJkOTlcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWM2N2NcdWNhYmQgXHVjMjJiXHVjNzkwXHViMjk0IEksIFgsIEMgXHViZmQwXHVjNzc0XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWJlODRcdWMxNDggXHViYzk1XHVjZTU5XHVjNWQwXHVjMTFjIElcdWIyOTQgViBcLyBYIFx1YzYwNlx1YzVkMFx1YjljYywgWFx1YjI5NCBMIFwvIEMgXHVjNjA2XHVjNWQwXHViOWNjLCBDXHViMjk0IEQgXC8gTSBcdWM2MDZcdWM1ZDBcdWI5Y2MgXHVjNjJjIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHVjNzc0IFx1YWRkY1x1Y2U1OVx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIyOTQgXHViODVjXHViOWM4XHVjMjJiXHVjNzkwXHViNGU0XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljOCBcdWI1NGMgXHVjNzc0XHViOTdjIFx1YzJlZFx1YzljNFx1YzIxOCBcdWM4MTVcdWMyMThcdWI4NWMgXHViYzE0XHVhZmI4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIE5cdWM3NDAgXHViY2MwXHVhY2JkXHVkNTYwIFx1Yjg1Y1x1YjljOCBcdWMyMmJcdWM3OTBcdWM3NTggXHVjMjE4XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWQ2YzQgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHViODVjXHViOWM4XHVjMjJiXHVjNzkwXHVhYzAwIFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yjg1Y1x1YjljOFx1YzIyYlx1Yzc5MFx1YjI5NCBcdWM3MDRcdWM1ZDAgXHVjODAxXHVkNjAwXHVjNzg4XHViMjk0IFx1YWRkY1x1Y2U1OVx1Yzc0NCBcdWI1MzBcdWI5NzRcdWJhNzAgMTAwMDAgXHVjNzc0XHVkNTU4XHVjNzU4IFx1Yzc5MFx1YzVmMFx1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWM4ZmNcdWM1YjRcdWM5YzBcdWIyOTQgXHViODVjXHViOWM4XHVjMjJiXHVjNzkwXHViOTdjIDEwXHVjOWM0XHVjMjE4IFx1YzgxNVx1YzIxOFx1Yjg1YyBcdWJjMTRcdWFmYjhcdWM1YjRcdWMxMWMgXHVkNTVjIFx1YzkwNFx1YzUyOSBcdWNkOWNcdWI4MjVcdWQ1NThcdWI3N2MuPFwvcD5cclxuIiwiaGludCI6IjxwPkRhZnQgUHVuayAtIFZlcmlkaXMgUXVvPFwvcD5cclxuXHJcbjxwPjxpZnJhbWUgZnJhbWVib3JkZXI9XCIwXCIgaGVpZ2h0PVwiMzE1XCIgc3JjPVwiaHR0cHM6XC9cL3d3dy55b3V0dWJlLmNvbVwvZW1iZWRcL09nY1k2cWx6ZGY4XCIgd2lkdGg9XCI0MjBcIj48XC9pZnJhbWU+PFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI0NTMxIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiVmVyZGlzIFF1byIsImRlc2NyaXB0aW9uIjoiPHA+VGhlIFJvbWFucyB1c2VkIGxldHRlcnMgZnJvbSB0aGVpciBMYXRpbiBhbHBoYWJldCB0byByZXByZXNlbnQgZWFjaCBvZiB0aGUgc2V2ZW4gbnVtZXJhbHMgaW4gdGhlaXIgbnVtYmVyIHN5c3RlbS4gVGhlIGxpc3QgYmVsb3cgc2hvd3Mgd2hpY2ggbGV0dGVycyB0aGV5IHVzZWQgYW5kIHdoYXQgbnVtZXJpYyB2YWx1ZSBlYWNoIG9mIHRob3NlIGxldHRlcnMgcmVwcmVzZW50czo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5JID0gMTxcL2xpPlxyXG5cdDxsaT5WID0gNTxcL2xpPlxyXG5cdDxsaT5YID0gMTA8XC9saT5cclxuXHQ8bGk+TCA9IDUwPFwvbGk+XHJcblx0PGxpPkMgPSAxMDA8XC9saT5cclxuXHQ8bGk+RCA9IDUwMDxcL2xpPlxyXG5cdDxsaT5NID0gMTAwMDxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlVzaW5nIHRoZXNlIHNldmVuIG51bWVyYWxzLCBhbnkgZGVzaXJlZCBudW1iZXIgY2FuIGJlIGZvcm1lZCBieSBmb2xsb3dpbmcgdGhlIHR3byBiYXNpYyBhZGRpdGl2ZSBhbmQgc3VidHJhY3RpdmUgcnVsZXMuIFRvIGZvcm0gYSBudW1iZXIgdXNpbmcgdGhlIGFkZGl0aXZlIHJ1bGUgdGhlIFJvbWFuIG51bWVyYWxzIGFyZSBzaW1wbHkgd3JpdHRlbiBmcm9tIGxlZnQgdG8gcmlnaHQgaW4gZGVzY2VuZGluZyBvcmRlciwgYW5kIHRoZSB2YWx1ZSBvZiBlYWNoIHJvbWFuIG51bWVyYWwgaXMgYWRkZWQgdG9nZXRoZXIuIEZvciBleGFtcGxlLCB0aGUgbnVtYmVyIE1NQ0xWSUkgaGFzIHRoZSB2YWx1ZSAxMDAwICsgMTAwMCArIDEwMCArIDUwICsgNSArIDEgKyAxID0gMjE1Ny4gVXNpbmcgdGhlIGFkZGl0aW9uIHJ1bGUgYWxvbmUgY291bGQgbGVhZCB0byB2ZXJ5IGxvbmcgc3RyaW5ncyBvZiBsZXR0ZXJzLCBzbyB0aGUgc3VidHJhY3Rpb24gcnVsZSB3YXMgaW52ZW50ZWQgYXMgYSByZXN1bHQuIFVzaW5nIHRoaXMgcnVsZSwgYSBzbWFsbGVyIFJvbWFuIG51bWVyYWwgdG8gdGhlIGxlZnQgb2YgYSBsYXJnZXIgb25lIGlzIHN1YnRyYWN0ZWQgZnJvbSB0aGUgdG90YWwuIEluIG90aGVyIHdvcmRzLCB0aGUgbnVtYmVyIE1DTVhJViBpcyBpbnRlcnByZXRlZCBhcyAxMDAwICZtaW51czsgMTAwICsgMTAwMCArIDEwICZtaW51czsgMSArIDUgPSAxOTE0LjxcL3A+XHJcblxyXG48cD5PdmVyIHRpbWUgdGhlIFJvbWFuIG51bWJlciB3cml0aW5nIHN5c3RlbSBiZWNhbWUgbW9yZSBzdGFuZGFyZGl6ZWQgYW5kIHNldmVyYWwgYWRkaXRpb25hbCBydWxlcyB3ZXJlIGRldmVsb3BlZC4gVGhlIGFkZGl0aW9uYWwgcnVsZXMgdXNlZCB0b2RheSBhcmU6PFwvcD5cclxuXHJcbjxvbD5cclxuXHQ8bGk+VGhlIEksIFgsIG9yIEMgUm9tYW4gbnVtZXJhbHMgbWF5IG9ubHkgYmUgcmVwZWF0ZWQgdXAgdG8gdGhyZWUgdGltZXMgaW4gc3VjY2Vzc2lvbi4gSW4gb3RoZXIgd29yZHMsIHRoZSBudW1iZXIgNCBtdXN0IGJlIHJlcHJlc2VudGVkIGFzIElWIGFuZCBub3QgYXMgSUlJSS48XC9saT5cclxuXHQ8bGk+VGhlIFYsIEwsIG9yIEQgbnVtZXJhbHMgbWF5IG5ldmVyIGJlIHJlcGVhdGVkIGluIHN1Y2Nlc3Npb24sIGFuZCB0aGUgTSBudW1lcmFsIG1heSBiZSByZXBlYXRlZCBhcyBtYW55IHRpbWVzIGFzIG5lY2Vzc2FyeS48XC9saT5cclxuXHQ8bGk+T25seSBvbmUgc21hbGxlciBudW1lcmFsIGNhbiBiZSBwbGFjZWQgdG8gdGhlIGxlZnQgb2YgYW5vdGhlci4gRm9yIGV4YW1wbGUsIHRoZSBudW1iZXIgMTggaXMgcmVwcmVzZW50ZWQgYXMgWFZJSUkgYnV0IG5vdCBhcyBYSUlYLjxcL2xpPlxyXG5cdDxsaT5Pbmx5IHRoZSBJLCBYLCBvciBDIGNhbiBiZSB1c2VkIGFzIHN1YnRyYWN0aXZlIG51bWVyYWxzLjxcL2xpPlxyXG5cdDxsaT5BIHN1YnRyYWN0aXZlIEkgY2FuIG9ubHkgYmUgdXNlZCB0byB0aGUgbGVmdCBvZiBhIFYgb3IgWC4gTGlrZXdpc2UgYSBYIGNhbiBvbmx5IGFwcGVhciB0byB0aGUgbGVmdCBvZiBhIEwgb3IgQywgYW5kIGEgQyBjYW4gb25seSBiZSB1c2VkIHRvIHRoZSBsZWZ0IG9mIGEgRCBvciBNLiBGb3IgZXhhbXBsZSwgNDkgbXVzdCBiZSB3cml0dGVuIGFzIFhMSVggYW5kIG5vdCBhcyBJTC48XC9saT5cclxuPFwvb2w+XHJcblxyXG48cD5Zb3VyIGdvYWwgaXMgdG8gd3JpdGUgYSBwcm9ncmFtIHdoaWNoIGNvbnZlcnRzIFJvbWFuIG51bWJlcnMgdG8gYmFzZSAxMCBpbnRlZ2Vycy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCB0byB0aGlzIHByb2JsZW0gd2lsbCBjb25zaXN0IG9mIHRoZSBmb2xsb3dpbmc6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+QSBsaW5lIHdpdGggYSBzaW5nbGUgaW50ZWdlciAmcXVvdDtOJnF1b3Q7ICgxICZsZTsgTiAmbGU7IDEwMDApLCB3aGVyZSBOIGluZGljYXRlcyBob3cgbWFueSBSb21hbiBudW1iZXJzIGFyZSB0byBiZSBjb252ZXJ0ZWQuPFwvbGk+XHJcblx0PGxpPkEgc2VyaWVzIG9mIE4gbGluZXMgb2YgaW5wdXQgd2l0aCBlYWNoIGxpbmUgY29udGFpbmluZyBvbmUgUm9tYW4gbnVtYmVyLiBFYWNoIFJvbWFuIG51bWJlciB3aWxsIGJlIGluIHRoZSByYW5nZSBvZiAxIHRvIDEwLDAwMCAoaW5jbHVzaXZlKSBhbmQgd2lsbCBvYmV5IGFsbCBvZiB0aGUgcnVsZXMgbGFpZCBvdXQgaW4gdGhlIHByb2JsZW0mIzM5O3MgaW50cm9kdWN0aW9uLjxcL2xpPlxyXG48XC91bD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggb2YgdGhlIE4gUm9tYW4gbnVtYmVycywgcHJpbnQgdGhlIGVxdWl2YWxlbnQgYmFzZSAxMCBpbnRlZ2VyLCBvbmUgcGVyIGxpbmUuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d