ISBN Conversion

An ISBN (International Standard Book Number) is a unique identifier assigned to each distinct edition or version of a published book. For example, the hardcover and paperback editions of the same book get different ISBNs. ISBNs assigned before 2007 are 10 digits long (the ISBN-10 standard), and ISBNs assigned on or after January 1, 2007, are 13 digits long (the ISBN-13 standard).

Some books issued before 2007 that are still in print have both an original ISBN-10 and a matching ISBN-13. Some newer books also receive both an ISBN-10 and an ISBN-13, the former for backward compatibility. This problem is based on that dual numbering and asks you to convert valid ISBN-10s to their corresponding ISBN-13s.

The last digit of any ISBN is a checksum digit used for simple error detection. ISBN-10 and ISBN-13 use different rules to compute and verify it.

1. ISBN-10: Let the 10 digits from left to right be $d_1, d_2, \ldots, d_{10}$ ($d_{10}$ is the checksum digit), and let $S = 10 \cdot d_1 + 9 \cdot d_2 + 8 \cdot d_3 + \ldots + 2 \cdot d_9 + 1 \cdot d_{10}$ (the coefficients decrease from 10 to 1). Then $S$ must be a multiple of 11, i.e., $S \equiv 0 \pmod{11}$.
2. ISBN-13: Let the 13 digits from left to right be $d_1, d_2, \ldots, d_{13}$ ($d_{13}$ is the checksum digit), and let $S = 1 \cdot d_1 + 3 \cdot d_2 + 1 \cdot d_3 + 3 \cdot d_4 + \ldots + 3 \cdot d_{12} + 1 \cdot d_{13}$ (odd-indexed digits are multiplied by 1, and even-indexed digits by 3). Then $S$ must be a multiple of 10, i.e., $S \equiv 0 \pmod{10}$.

Each rule uniquely determines the checksum digit given the other digits.

X Factor: One detail applies to ISBN-10 but not to ISBN-13. Because the modulus is 11, the checksum digit can take a value in $\{0, 1, 2, \ldots, 9, 10\}$. When the value is 10, it is written as X so that only one character is needed. For example, $039428013\textrm{X}$ is a valid ISBN-10.

Hyphens: Technically, an ISBN-10 has four parts, one of which is the checksum digit. (The rules for the first three parts are complicated, so this problem does not cover them.) Two adjacent parts can optionally be separated by a hyphen, so an ISBN-10 may contain up to three hyphens. It cannot begin or end with a hyphen, and it cannot contain consecutive hyphens. If there are three hyphens, one must separate the checksum digit from the digit before it. If there are fewer than three hyphens, there may or may not be a hyphen between the checksum digit and the digit before it. For this problem, the following are valid ISBN-10s:

$039428013\textrm{-X}$

$0\textrm{-}39\textrm{-}428013\textrm{X}$

$3\textrm{-}540\textrm{-}42580\textrm{-}2$

$3540425802$

The following are invalid ISBN-10s. The first two have hyphen placement errors, and the last fails the checksum test above:

$3\textrm{-}540\textrm{-}4258\textrm{-}02$

$3\textrm{-}540\textrm{-}425802\textrm{-}$

$0\textrm{-}14\textrm{-}028333\textrm{-}3$

To convert an ISBN-10 to an ISBN-13, (i) prepend the three digits $978$, (ii) remove the old checksum digit, and (iii) append a new checksum digit determined by the ISBN-13 rule.[1] To keep things simple, keep the positions of any existing hyphens, and put a hyphen after the prepended 978.

1 An ISBN-13 can begin with three digits other than 978, but only 978 can be prepended to an ISBN-10 to form the matching ISBN-13.

The first line contains an integer $T$ $(1 \leq T \leq 25)$, the number of (possibly invalid) ISBN-10s to process. This is followed by $T$ lines. Each line contains a nonempty string of length 10 to 13, inclusive. Each character is a decimal digit ('0' to '9'), a hyphen ('-'), or a capital X.

For each test case, if the candidate ISBN-10 is not valid under the rules above, print "invalid" on its own line. Otherwise, print the corresponding ISBN-13 on its own line.