시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 20 17 12 85.714%

문제

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

  • 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+XHVjY2FiXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gTlx1Yzc0MCBcdWJjYzBcdWFjYmRcdWQ1NjAgXHViODVjXHViOWM4IFx1YzIyYlx1Yzc5MFx1Yzc1OCBcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NFx1ZDZjNCBOXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBcdWI4NWNcdWI5YzhcdWMyMmJcdWM3OTBcdWFjMDAgXHVkNTU4XHViMDk4XHVjNTI5IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViODVjXHViOWM4XHVjMjJiXHVjNzkwXHViMjk0IFx1YzcwNFx1YzVkMCBcdWM4MDFcdWQ2MDBcdWM3ODhcdWIyOTQgXHVhZGRjXHVjZTU5XHVjNzQ0IFx1YjUzMFx1Yjk3NFx1YmE3MCAxMDAwMCBcdWM3NzRcdWQ1NThcdWM3NTggXHVjNzkwXHVjNWYwXHVjMjE4XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YzhmY1x1YzViNFx1YzljMFx1YjI5NCBcdWI4NWNcdWI5YzhcdWMyMmJcdWM3OTBcdWI5N2MgMTBcdWM5YzRcdWMyMTggXHVjODE1XHVjMjE4XHViODVjIFx1YmMxNFx1YWZiOFx1YzViNFx1YzExYyBcdWQ1NWMgXHVjOTA0XHVjNTI5IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1Yjc3Yy48XC9wPlxyXG4iLCJoaW50IjoiPHA+RGFmdCBQdW5rIC0gVmVyaWRpcyBRdW88XC9wPlxyXG5cclxuPHA+PGlmcmFtZSBmcmFtZWJvcmRlcj1cIjBcIiBoZWlnaHQ9XCIzMTVcIiBzcmM9XCJodHRwczpcL1wvd3d3LnlvdXR1YmUuY29tXC9lbWJlZFwvT2djWTZxbHpkZjhcIiB3aWR0aD1cIjQyMFwiPjxcL2lmcmFtZT48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjQ1MzEiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJWZXJkaXMgUXVvIiwiZGVzY3JpcHRpb24iOiI8cD5UaGUgUm9tYW5zIHVzZWQgbGV0dGVycyBmcm9tIHRoZWlyIExhdGluIGFscGhhYmV0IHRvIHJlcHJlc2VudCBlYWNoIG9mIHRoZSBzZXZlbiBudW1lcmFscyBpbiB0aGVpciBudW1iZXIgc3lzdGVtLiBUaGUgbGlzdCBiZWxvdyBzaG93cyB3aGljaCBsZXR0ZXJzIHRoZXkgdXNlZCBhbmQgd2hhdCBudW1lcmljIHZhbHVlIGVhY2ggb2YgdGhvc2UgbGV0dGVycyByZXByZXNlbnRzOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPkkgPSAxPFwvbGk+XHJcblx0PGxpPlYgPSA1PFwvbGk+XHJcblx0PGxpPlggPSAxMDxcL2xpPlxyXG5cdDxsaT5MID0gNTA8XC9saT5cclxuXHQ8bGk+QyA9IDEwMDxcL2xpPlxyXG5cdDxsaT5EID0gNTAwPFwvbGk+XHJcblx0PGxpPk0gPSAxMDAwPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+VXNpbmcgdGhlc2Ugc2V2ZW4gbnVtZXJhbHMsIGFueSBkZXNpcmVkIG51bWJlciBjYW4gYmUgZm9ybWVkIGJ5IGZvbGxvd2luZyB0aGUgdHdvIGJhc2ljIGFkZGl0aXZlIGFuZCBzdWJ0cmFjdGl2ZSBydWxlcy4gVG8gZm9ybSBhIG51bWJlciB1c2luZyB0aGUgYWRkaXRpdmUgcnVsZSB0aGUgUm9tYW4gbnVtZXJhbHMgYXJlIHNpbXBseSB3cml0dGVuIGZyb20gbGVmdCB0byByaWdodCBpbiBkZXNjZW5kaW5nIG9yZGVyLCBhbmQgdGhlIHZhbHVlIG9mIGVhY2ggcm9tYW4gbnVtZXJhbCBpcyBhZGRlZCB0b2dldGhlci4gRm9yIGV4YW1wbGUsIHRoZSBudW1iZXIgTU1DTFZJSSBoYXMgdGhlIHZhbHVlIDEwMDAgKyAxMDAwICsgMTAwICsgNTAgKyA1ICsgMSArIDEgPSAyMTU3LiBVc2luZyB0aGUgYWRkaXRpb24gcnVsZSBhbG9uZSBjb3VsZCBsZWFkIHRvIHZlcnkgbG9uZyBzdHJpbmdzIG9mIGxldHRlcnMsIHNvIHRoZSBzdWJ0cmFjdGlvbiBydWxlIHdhcyBpbnZlbnRlZCBhcyBhIHJlc3VsdC4gVXNpbmcgdGhpcyBydWxlLCBhIHNtYWxsZXIgUm9tYW4gbnVtZXJhbCB0byB0aGUgbGVmdCBvZiBhIGxhcmdlciBvbmUgaXMgc3VidHJhY3RlZCBmcm9tIHRoZSB0b3RhbC4gSW4gb3RoZXIgd29yZHMsIHRoZSBudW1iZXIgTUNNWElWIGlzIGludGVycHJldGVkIGFzIDEwMDAgJm1pbnVzOyAxMDAgKyAxMDAwICsgMTAgJm1pbnVzOyAxICsgNSA9IDE5MTQuPFwvcD5cclxuXHJcbjxwPk92ZXIgdGltZSB0aGUgUm9tYW4gbnVtYmVyIHdyaXRpbmcgc3lzdGVtIGJlY2FtZSBtb3JlIHN0YW5kYXJkaXplZCBhbmQgc2V2ZXJhbCBhZGRpdGlvbmFsIHJ1bGVzIHdlcmUgZGV2ZWxvcGVkLiBUaGUgYWRkaXRpb25hbCBydWxlcyB1c2VkIHRvZGF5IGFyZTo8XC9wPlxyXG5cclxuPG9sPlxyXG5cdDxsaT5UaGUgSSwgWCwgb3IgQyBSb21hbiBudW1lcmFscyBtYXkgb25seSBiZSByZXBlYXRlZCB1cCB0byB0aHJlZSB0aW1lcyBpbiBzdWNjZXNzaW9uLiBJbiBvdGhlciB3b3JkcywgdGhlIG51bWJlciA0IG11c3QgYmUgcmVwcmVzZW50ZWQgYXMgSVYgYW5kIG5vdCBhcyBJSUlJLjxcL2xpPlxyXG5cdDxsaT5UaGUgViwgTCwgb3IgRCBudW1lcmFscyBtYXkgbmV2ZXIgYmUgcmVwZWF0ZWQgaW4gc3VjY2Vzc2lvbiwgYW5kIHRoZSBNIG51bWVyYWwgbWF5IGJlIHJlcGVhdGVkIGFzIG1hbnkgdGltZXMgYXMgbmVjZXNzYXJ5LjxcL2xpPlxyXG5cdDxsaT5Pbmx5IG9uZSBzbWFsbGVyIG51bWVyYWwgY2FuIGJlIHBsYWNlZCB0byB0aGUgbGVmdCBvZiBhbm90aGVyLiBGb3IgZXhhbXBsZSwgdGhlIG51bWJlciAxOCBpcyByZXByZXNlbnRlZCBhcyBYVklJSSBidXQgbm90IGFzIFhJSVguPFwvbGk+XHJcblx0PGxpPk9ubHkgdGhlIEksIFgsIG9yIEMgY2FuIGJlIHVzZWQgYXMgc3VidHJhY3RpdmUgbnVtZXJhbHMuPFwvbGk+XHJcblx0PGxpPkEgc3VidHJhY3RpdmUgSSBjYW4gb25seSBiZSB1c2VkIHRvIHRoZSBsZWZ0IG9mIGEgViBvciBYLiBMaWtld2lzZSBhIFggY2FuIG9ubHkgYXBwZWFyIHRvIHRoZSBsZWZ0IG9mIGEgTCBvciBDLCBhbmQgYSBDIGNhbiBvbmx5IGJlIHVzZWQgdG8gdGhlIGxlZnQgb2YgYSBEIG9yIE0uIEZvciBleGFtcGxlLCA0OSBtdXN0IGJlIHdyaXR0ZW4gYXMgWExJWCBhbmQgbm90IGFzIElMLjxcL2xpPlxyXG48XC9vbD5cclxuXHJcbjxwPllvdXIgZ29hbCBpcyB0byB3cml0ZSBhIHByb2dyYW0gd2hpY2ggY29udmVydHMgUm9tYW4gbnVtYmVycyB0byBiYXNlIDEwIGludGVnZXJzLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IHRvIHRoaXMgcHJvYmxlbSB3aWxsIGNvbnNpc3Qgb2YgdGhlIGZvbGxvd2luZzo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5BIGxpbmUgd2l0aCBhIHNpbmdsZSBpbnRlZ2VyICZxdW90O04mcXVvdDsgKDEgJmxlOyBOICZsZTsgMTAwMCksIHdoZXJlIE4gaW5kaWNhdGVzIGhvdyBtYW55IFJvbWFuIG51bWJlcnMgYXJlIHRvIGJlIGNvbnZlcnRlZC48XC9saT5cclxuXHQ8bGk+QSBzZXJpZXMgb2YgTiBsaW5lcyBvZiBpbnB1dCB3aXRoIGVhY2ggbGluZSBjb250YWluaW5nIG9uZSBSb21hbiBudW1iZXIuIEVhY2ggUm9tYW4gbnVtYmVyIHdpbGwgYmUgaW4gdGhlIHJhbmdlIG9mIDEgdG8gMTAsMDAwIChpbmNsdXNpdmUpIGFuZCB3aWxsIG9iZXkgYWxsIG9mIHRoZSBydWxlcyBsYWlkIG91dCBpbiB0aGUgcHJvYmxlbSYjMzk7cyBpbnRyb2R1Y3Rpb24uPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBvZiB0aGUgTiBSb21hbiBudW1iZXJzLCBwcmludCB0aGUgZXF1aXZhbGVudCBiYXNlIDEwIGludGVnZXIsIG9uZSBwZXIgbGluZS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=