这是一个交互式问题。
在枯燥的拉丁语课上，Julius 和 Octavian 正在玩以下游戏。黑板上写着一个有效的非空罗马数字。
下表展示了罗马数字的写法：
| 个位数值 | 千位 | 百位 | 十位 | 个位 |
|---|---|---|---|---|
| 1 | M | C | X | I |
| 2 | MM | CC | XX | II |
| 3 | MMM | CCC | XXX | III |
| 4 | CD | XL | IV | |
| 5 | D | L | V | |
| 6 | DC | LX | VI | |
| 7 | DCC | LXX | VII | |
| 8 | DCCC | LXXX | VIII | |
| 9 | CM | XC | IX |
组成规则：
- 4, 9, 40, 90, 400 和 900 使用“减法记数法”书写，即较小的符号从较大的符号中减去：例如，40 (“XL”) 写为 ‘X’ (10) 从 ‘L’ (50) 中减去。这是标准用法中仅有的减法形式。
- 包含多个十进制位的数字是通过从高位到低位依次拼接对应的罗马数字构成的。
- 任何缺失的数位（在位值表示中为零）将被省略。
- 罗马数字能表示的最大数字是 3999 (MMMCMXCIX)。
Julius 可以选择谁先手。然后玩家轮流进行操作。一次操作包括在黑板上已有的数字的左侧或右侧添加一个字母，使得结果仍然是一个有效的罗马数字。无法进行下一步操作的玩家输掉比赛。
你的任务是，给定初始数字，在代表 Julius 进行游戏时获胜，计算机将代表 Octavian 进行游戏。你可以选择你的先后手（先手或后手）。
交互
一个测试包含多个场景。首先，评测程序打印一行包含一个整数 $t$，即场景的数量 ($1 \le t \le 100$)。
在每个场景中，交互以评测程序打印一行有效的非空罗马数字开始。然后，参与者选择先手玩家：参与者自己 (Julius) 或计算机 (Octavian)。为此，参与者打印一行包含一个整数：如果参与者先手，则打印 1；如果计算机先手，则打印 2。之后玩家轮流进行操作，打印操作后的罗马数字。每次操作打印在单独的一行上。
如果数字不是有效的罗马数字，或者如果数字不能通过在之前数字的左侧或右侧添加一个字母得到，则对应的玩家输掉比赛。评测程序不会尝试进行无效操作。相反，如果评测程序输了，它会在单独的一行输出 GG，并继续处理下一个场景（如果有的话），或者终止程序。
评测程序可以使用多种策略，其行为可能取决于参与者的操作（即交互器是自适应的）。
样例
输入格式 1
2 MMII MMMII GG MMIV GG
输出格式 1
2 MMMIII 1 MMMIV