题目描述

ISBN（International Standard Book Number，国际标准书号）是分配给已出版图书某一特定版本的唯一标识符。例如，同一版图书的精装本与平装本会获得不同的 ISBN。2007 年以前分配的 ISBN 长 $10$ 位，采用 ISBN-10 标准；从 2007 年 1 月 1 日起分配的 ISBN 长 $13$ 位，采用 ISBN-13 标准。

有些 2007 年以前出版且仍在印刷的图书，既有原来的 ISBN-10，也有与之对应的 ISBN-13；有些较新的图书也会同时获得 ISBN-10 和 ISBN-13，其中 ISBN-10 用于向后兼容。本题正是基于这种“双重身份”：你需要把合法的 ISBN-10 转换为与之对应的 ISBN-13。

任何 ISBN 的最后一位都是校验位，可用于简单的错误检测。ISBN-10 和 ISBN-13 计算及验证最后一位的规则不同。

1. ISBN-10：设从左到右的 $10$ 位数字依次为 $d_1,d_2,\ldots,d_{10}$，其中 $d_{10}$ 为校验位。定义

   $$S=10d_1+9d_2+8d_3+\cdots+2d_9+d_{10}$$

   各位的系数从 $10$ 递减至 $1$。$S$ 必须是 $11$ 的倍数，即 $S\equiv 0\pmod{11}$。

2. ISBN-13：设从左到右的 $13$ 位数字依次为 $d_1,d_2,\ldots,d_{13}$，其中 $d_{13}$ 为校验位。定义

   $$S=d_1+3d_2+d_3+3d_4+\cdots+3d_{12}+d_{13}$$

   奇数位置上的数字乘以 $1$，偶数位置上的数字乘以 $3$。$S$ 必须是 $10$ 的倍数，即 $S\equiv 0\pmod{10}$。

容易看出，对于这两种规则，在其他各位数字给定后，校验位都是唯一确定的。

关于 X： ISBN-10 有一个不适用于 ISBN-13、虽小却很重要的细节。由于其模数为 $11$，校验位的值属于集合 $\{0,1,2,\ldots,9,10\}$。当校验位的值为 $10$ 时，为了只使用一个字符，将其写成大写字母 X。例如，039428013X 是一个合法的 ISBN-10。

关于连字符： 严格来说，一个 ISBN-10 由四个部分组成，其中一部分是校验位。（前三部分的准确划分规则很复杂，本题不予讨论。）相邻两部分之间可以用连字符分隔，因此 ISBN-10 最多可以包含三个连字符，但不能以连字符开头或结尾，也不能包含连续的两个连字符。

如果 ISBN-10 中有三个连字符，则其中一个必须将校验位与它前面的数字分隔开；如果少于三个连字符，则校验位与它前面的数字之间可以有连字符，也可以没有。

因此，就本题而言，下面这些 ISBN-10 是合法的：

• 039428013-X
• 0-39-428013X
• 3-540-42580-2
• 3540425802

下面这些 ISBN-10 则是不合法的。前两个的连字符位置错误，最后一个不满足上述校验规则：

• 3-540-4258-02
• 3-540-425802-
• 0-14-028333-3

把 ISBN-10 转换为 ISBN-13 的方法如下：

1. 在开头添加三位数字 978；
2. 删除原有校验位；
3. 按 ISBN-13 规则计算并在末尾添加新的校验位。

为简化处理，应保持所有原有连字符的位置，并在新添加的 978 之后加上一个连字符。

注：一般而言，ISBN-13 开头的三位数字也可能不是 978，但要由 ISBN-10 得到与之对应的 ISBN-13，只能添加 978。

输入格式

第一行包含一个整数 $T$，表示需要处理的候选 ISBN-10 数量，其中 $1\le T\le 25$。

接下来 $T$ 行，每行包含一个非空字符串，长度在 $10$ 到 $13$ 之间。每个字符都是十进制数字（0 到 9）、连字符 - 或大写字母 X 之一。

输出格式

对于每组测试用例，如果候选 ISBN-10 按上述规则判定为不合法，输出一行 invalid；否则输出一行与之对应的 ISBN-13。

4
3-540-4258-02
039428013X
3-540-42580-2
0-14-028333-3

invalid
978-0394280134
978-3-540-42580-9
invalid