FBI 最近更改了其用于识别 FBI 指纹数据库中个人的通用控制号码 (UCN)，改为一个八位的 27 进制数值，并附带一个第九位的校验位。所使用的数字为：

0123456789ACDEFHJKLMNPRTVWX

由于可能与其他数字混淆，某些字母不被使用：

B->8, G->C, I->1, O->0, Q->0, S->5, U->V, Y->V, Z->2

校验位计算公式如下：

$$(2 \times D_1 + 4 \times D_2 + 5 \times D_3 + 7 \times D_4 + 8 \times D_5 + 10 \times D_6 + 11 \times D_7 + 13 \times D_8) \pmod{27}$$

其中 $D_n$ 是从左往右数的第 $n$ 位数字。

这种校验位的选择可以检测出原始八位数字中的任何单数字错误以及任何相邻数字对的转置错误。

对于本题，你需要编写一个程序来解析用户输入的 UCN。你的程序应接受十进制数字和任何大写字母作为数字。如果输入中出现了上述“易混淆”字母，你应该将其替换为列表中对应的有效数字。你的程序应计算正确的校验位并将其与输入的校验位进行比较。如果两者不匹配，则拒绝该输入；否则，返回前八位数字对应的十进制（基数为 10）数值。

输入格式

输入的第一行包含一个十进制整数 $P$ ($1 \le P \le 10000$)，表示后续的数据集数量。每个数据集应被独立且相同地处理。

每个数据集由单行输入组成。它包含数据集编号 $K$，后跟一个空格，再后跟 9 个十进制数字或大写（字母）字符。

输出格式

对于每个数据集，输出一行。该单行输出包含数据集编号 $K$，后跟一个空格，再后跟字符串 “Invalid”（不含引号）或前八位数字对应的十进制数值。

样例

样例输入 1

3
1 12345678A
2 12435678A
3 12355678A

样例输出 1

1 11280469652
2 Invalid
3 Invalid