Khôi có một cuốn sách cổ của người La Mã. Nó luôn luôn sử dụng các chữ số La Mã để đánh số trang. Và quyển sách của nó không bao giờ có hơn 3999 trang. Khi cần thiết, sách được chia thành các tập.

Bạn phải viết một chương trình, cho một số hệ thập phân, hiển thị tương đương của nó bằng chữ số La Mã.

Số La Mã gồm 7 kí tự tương ứng với các số thập phân sau:

Người ta quy định các chữ số I, X, C, M không được lặp lại quá ba lần liên tiếp và các kí tự V, L, D không được lặp lại quá một lần liên tiếp. Chính vì thế mà có 6 nhóm kí tự đặc biệt được nêu ra trong bảng sau:

Quy tắc viết: ký tự lớn viết trước, ký tự nhỏ viết sau tương tự như hàng ngàn, hàng trăm, hàng chục, hàng đơn vị trong số thập phân. Với các ký tự trên, số La Mã có thể biểu diễn được các số thập phân từ 1 đến 3999.

Ví dụ: III = 3, VIII = 8, XIX = 19, XXXII = 32, XLV = 45, MMM = 3000

Input

• Dòng 1 là một số nguyên dương \(T\) (\(1 \le T \le 10\)) là số bộ test.
• \(T\) dòng tiếp theo, dòng thứ \(i\) là số nguyên dương \(N\) (\(1 \le N < 4000\)) biểu thị cho quyển sách thứ \(i\) có \(N\) trang.

Output

• In ra trên \(T\) dòng, dòng thứ \(i\) là kết quả tương ứng test thứ \(i\) với số \(N\) được viết bằng chữ số La Mã trong một dòng đơn. Luôn luôn sử dụng chữ in hoa.

Example

2
666
83

DCLXVI
LXXXIII