Roman Numeral Sentences

Roman numerals use the following seven symbols.

A Roman numeral must satisfy all of these rules.

• A larger symbol is usually written to the left of a smaller symbol. The value is then the sum of all symbols. For example, LX is 50 + 10 = 60, and MLI is 1000 + 50 + 1 = 1051.
• V, L, and D may be used only once. I, X, and C may appear consecutively at most three times, while M may be used any number of times. Repeated equal symbols add their values; for example, XXX is 30 and CCLIII is 253.
• A smaller symbol may appear to the left of a larger symbol only in IV = 4, IX = 9, XL = 40, XC = 90, CD = 400, and CM = 900. The two subtractive forms for the same digit cannot be used together: IV with IX, XL with XC, or CD with CM. Apart from these cases, a smaller symbol cannot appear to the left of a larger one.
• Every number must be written with as few Roman numeral symbols as possible. For example, 60 is LX, not XLXX, and 5 is V, not IVI.

By these rules, 235 is CCXXXV, 1940 is MCMXL, and 5493 is MMMMMCDXCIII.

Some people hid Roman numerals inside English sentences by inserting other letters or spaces before, after, or between the Roman numeral symbols. If the letters m, d, c, l, x, v, i that correspond to a Roman numeral can be selected from a sentence in order, the sentence can be regarded as expressing that numeral. For example, matt is the best school in korea can express 1051 by selecting M, L, I in order. The order of letters cannot be changed, so mind control cannot express M, L, I.

A sentence may express more than one number. For example, matt is the best school in korea can also express 1151 by selecting M, C, L, I in order.

Given English sentences, write a program that finds the largest number each sentence can express. If a sentence cannot express any positive integer, output 0.

The first line contains the number of sentences N. (1 ≤ N ≤ 10)

Each of the next N lines contains one English sentence. Every sentence consists only of lowercase English letters and spaces, and its length is at most 10,000.

For each sentence, output the largest number it can express on its own line. If a sentence cannot be interpreted as any number, output 0.