小玛莎已经学会了计数，现在她正在学习罗马数字。在当今的用法中，罗马数字通常由大写字母组成的字符串表示，其对应的值如下：“I”为 1，“V”为 5，“X”为 10，“L”为 50，“C”为 100，“D”为 500，“M”为 1000。

我们从左到右阅读罗马数字。在简单的情况下，字母按值从大到小排列，数值等于所有字母值的总和。此外，有时较小的值会出现在较大的值之前，此时较小的值不加到结果中，而是从结果中减去：例如，“IV”的值为 4，“IX”的值为 9。遗憾的是，这些规则还设定了各种限制：例如，数字 4 表示为“IV”而不是“IIII”，数字 999 表示为“CMXCIX”而不是“IM”……

玛莎不喜欢普通罗马数字的限制，于是她发明了自己的记数法：自由罗马数字。这些数字也由具有相同值的相同字母组成的字符串表示，处理方式如下：从左到右考虑这些字母。每个字母将其值加到结果中。此外，如果一个字母 $c$ 的前面紧邻着一个值较小的字母，则执行以下操作：找到左侧距离最近的字母 $b$，使得其值不小于 $c$ 的值。之后，考虑 $b$ 和 $c$ 之间的字符串 $S$；如果没有这样的字母 $b$，则字符串 $S$ 从整个字符串的开头开始。求出 $S$ 作为自由罗马数字的数值。注意，此时 $S$ 的值已经被加到了结果中，现在将其改为减去（实际上，当前结果减少了 $S$ 值的两倍）。

自由罗马数字和普通罗马数字一样，仅用于正整数。因此，一个字符串只有在上述算法中字符串 $S$ 的值在任何情况下都严格小于字母 $c$ 的值时，才是一个有效的自由罗马数字。

举个例子，考虑自由罗马数字“XIIXL”。前三个字母“XII”分别将 10、1 和 1 加到结果中。下一个字母“X”也加 10，但随后将“II”（即 2）的加法替换为减法，因此结果现在为 $10 + 10 - 2 = 18$。最后，字母“L”将 50 加到结果中，然后将“XIIX”（即 18）的加法替换为减法，因此最终结果为 $50 - 18 = 32$。

玛莎为她的发明感到自豪：她设计了一个比普通罗马数字限制更少的系统，但每个普通罗马数字仍然可以按照玛莎的规则正确读取。她开始将数字从十进制记数法转换为自由罗马记数法，反之亦然，然后思考：如何为给定的数字找到最短的自由罗马记数法？玛莎放下笔，陷入了沉思。

请解决玛莎问题的通用版本。将给定的自由罗马记数法数字转换为十进制，并将给定的十进制数字转换为其最短的自由罗马记数法。

输入格式

输入包含 1 到 10 000 行。每一行表示一个 1 到 3000 之间的整数。每个数字要么以不含前导零的十进制形式给出，要么以自由罗马记数法给出：在这种情况下，该记数法是有效的，包含 1 到 20 个字母，但不一定是最短的。

输出格式

对于每一行输入，打印一行，输出该数字的另一种记数法。具体来说，如果数字以自由罗马记数法给出，则以不含前导零的十进制形式打印。如果数字以十进制给出，则打印其最短的自由罗马记数法。如果有多种可能的各种最短记数法，打印其中任意一种即可。

样例

样例输入 1

IIII
4
CMXCIX
999
XIIXL
32

样例输出 1

4
IV
999
IM
32
IIXXL