P17375 [ECNA 2023] ISBN Conversion

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。