ISBN（国际标准书号）是分配给已出版书籍的特定版本/形式的唯一标识符（例如，同一版本的精装本和平装本具有不同的 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-13。
任何 ISBN 的最后一位都是校验位，可用于简单的错误检测。ISBN-10 和 ISBN-13 使用不同的规则来计算/验证最后一位：
ISBN-10：如果从左到右的 10 位数字为 $d_1, d_2, \dots, d_{10}$（其中 $d_{10}$ 是校验位），且 $$S = 10 \cdot d_1 + 9 \cdot d_2 + 8 \cdot d_3 + \dots + 2 \cdot d_9 + 1 \cdot d_{10}$$ （系数从 10 递减到 1），则 $S$ 必须是 11 的倍数，即 $S \equiv 0 \pmod{11}$。
ISBN-13：如果从左到右的 13 位数字为 $d_1, d_2, \dots, d_{13}$（其中 $d_{13}$ 是校验位），且 $$S = 1 \cdot d_1 + 3 \cdot d_2 + 1 \cdot d_3 + 3 \cdot d_4 + \dots + 3 \cdot d_{12} + 1 \cdot d_{13}$$ （奇数位乘以 1，偶数位乘以 3），则 $S$ 必须是 10 的倍数，即 $S \equiv 0 \pmod{10}$。
不难看出，每条规则都能唯一确定校验位（给定其他数字的情况下）。
X 因子：注意 ISBN-10 的一个虽小但重要的细节，该细节不适用于 ISBN-13：由于模数为 11，校验位的值位于 $\{0, 1, 2, \dots, 9, 10\}$ 中。在校验位值为 10 的特殊情况下，它被写为 X，以便只需要一个字符。例如，039428013X 是一个有效的 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？只需 (i) 在前面加上数字 978，(ii) 去掉旧的校验位，以及 (iii) 按照 ISBN-13 规则附加一个新的校验位。为简单起见，保持现有连字符的位置，并在前缀 978 后面加上一个连字符。
输入格式
输入的第一行包含一个整数 $T$ ($1 \le T \le 25$)，表示要处理的（可能无效的）ISBN-10 的数量。随后是 $T$ 行，每行包含一个长度在 10 到 13 之间的非空字符串。每个字符要么是十进制数字（'0' 到 '9'），要么是连字符（'-'），要么是 'X'（大写 X）。
输出格式
对于每个测试用例，如果候选 ISBN-10 根据上述细节无效，则输出一行 "invalid"。否则，输出一行包含对应的 ISBN-13。
样例
样例输入 1
4 3-540-4258-02 039428013X 3-540-42580-2 0-14-028333-3
样例输出 1
invalid 978-0394280134 978-3-540-42580-9 invalid
Figure 1. An example of an ISBN-10 and its corresponding ISBN-13 barcode.