로마 숫자 문장

로마 숫자는 다음 7개의 기호로 수를 나타낸다.

로마 숫자는 아래 규칙을 모두 만족해야 한다.

• 보통 큰 값을 가진 기호를 왼쪽에, 작은 값을 가진 기호를 오른쪽에 쓴다. 이때 수의 값은 사용한 모든 기호의 값을 더한 값이다. 예를 들어 LX는 50 + 10 = 60이고, MLI는 1000 + 50 + 1 = 1051이다.
• V, L, D는 한 번만 사용할 수 있다. I, X, C는 연속해서 최대 세 번까지 사용할 수 있고, M은 원하는 만큼 사용할 수 있다. 같은 기호가 반복되면 각 기호의 값을 모두 더한다. 예를 들어 XXX는 30이고, CCLIII는 253이다.
• 작은 값을 가진 기호가 큰 값을 가진 기호의 왼쪽에 올 수 있는 경우는 IV = 4, IX = 9, XL = 40, XC = 90, CD = 400, CM = 900뿐이다. 같은 자리의 두 감산 표기는 함께 사용할 수 없다. 즉 IV와 IX, XL과 XC, CD와 CM은 각각 한 표기 안에서 동시에 쓰지 않는다. 이 경우를 제외하면 작은 기호가 큰 기호의 왼쪽에 올 수 없다.
• 모든 수는 가능한 가장 적은 수의 로마 숫자 기호로 표현해야 한다. 예를 들어 60은 LX이고 XLXX가 아니며, 5는 V이고 IVI가 아니다.

위 규칙에 따르면 235는 CCXXXV, 1940은 MCMXL, 5493은 MMMMMCDXCIII로 쓴다.

어떤 사람들은 로마 숫자 문자열의 앞, 뒤, 또는 문자 사이에 다른 문자와 공백을 넣어 영어 문장처럼 보이게 만들었다. 문장 안에서 로마 숫자에 해당하는 글자 m, d, c, l, x, v, i를 순서대로 골라낼 수 있으면, 그 문장은 그 로마 숫자를 표현한다고 본다. 예를 들어 matt is the best school in korea에서는 M, L, I를 순서대로 골라 1051을 표현할 수 있다. 문자의 순서는 바꿀 수 없으므로 mind control은 M, L, I를 순서대로 만들 수 없다.

한 문장이 여러 수를 표현할 수도 있다. 예를 들어 matt is the best school in korea에서는 M, C, L, I를 순서대로 골라 1151을 표현할 수도 있다.

영어 문장이 주어질 때, 그 문장이 표현할 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. 어떤 양의 정수도 표현할 수 없다면 0을 출력한다.

첫째 줄에 문장의 개수 N이 주어진다. (1 ≤ N ≤ 10)

다음 N개의 줄에는 영어 문장이 한 줄에 하나씩 주어진다. 각 문장은 알파벳 소문자와 공백으로만 이루어져 있으며, 길이는 10,000을 넘지 않는다.

각 문장마다 그 문장이 표현할 수 있는 가장 큰 수를 한 줄에 하나씩 출력한다. 어떤 수로도 볼 수 없는 문장은 0을 출력한다.