Figure 1. Barcode with ISBN-10 above and ISBN-13 below

An ISBN (International Standard Book Number) is a unique identifier assigned to a distinct edition/version of a published book (for example, hardcover and paperback versions of the same edition get different ISBNs).

ISBNs assigned before 2007 were $10$ digits long (the $\mbox{ISBN-10}$ standard), and ISBNs assigned on or after January 1, 2007, are $13$ digits long (the $\mbox{ISBN-13}$ standard). Some books issued before 2007 that are still in print have both an original $\mbox{ISBN-10}$ and a matching $\mbox{ISBN-13}$, and some newer books are also given both an $\mbox{ISBN-10}$ and an $\mbox{ISBN-13}$, the former for backward-compatibility purposes. That "double identity" situation is the basis for this problem, which requires you to convert valid $\mbox{ISBN-10s}$ to their corresponding $\mbox{ISBN-13s}$.

The last digit of any ISBN is a checksum digit that can be used for simple error detection. $\mbox{ISBN-10}$ and $\mbox{ISBN-13}$ use different rules for computing/verifying this last digit:

• $\mbox{ISBN-10}$: If the $10$ digits from left to right are $d_1, d_2, \ldots, d_{10}$ (so $d_{10}$ is the checksum digit), and if $[ S = 10 \cdot d_1 + 9 \cdot d_2 + 8 \cdot d_3 + \ldots + 2 \cdot d_9 + 1 \cdot d_{10} ]$ (coefficients decrease from $10$ to $1$), then $S$ must be a multiple $\textrm{of }11$, i.e., $S \equiv 0$ $(\textrm{mod }11)$.

• $\mbox{ISBN-13}$: If the $13$ digits from left to right are $d_1, d_2, \ldots, d_{13}$ (so $d_{13}$ is the checksum digit), and if $[ 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$, even-indexed digits are multiplied $\textrm{by }3$), then $S$ must be a multiple $\textrm{of }10$, i.e., $S \equiv 0$ $(\textrm{mod }10)$.

It is not hard to see that each rule uniquely determines the checksum digit (given the other digits).

X Factor: Note the following small but important detail for $\mbox{ISBN-10}$ that does not apply to $\mbox{ISBN-13}$: because the modulus $\textrm{is }11$, the value of the checksum digit lies in $\{0, 1, 2, \ldots, 9, 10\}$, and in the special case that the value of the checksum digit $\textrm{is }10$, it is written as X so that only one character is required. So, for example, $039428013\textrm{X}$ is a valid $\mbox{ISBN-10}$.

Hyphens: Technically an $\mbox{ISBN-10}$ consists of four parts, one of which is the checksum digit. (The exact rules defining the first three parts are complicated, so we will not deal with them here.) Two adjacent parts can optionally be separated by a hyphen, which means that an $\mbox{ISBN-10}$ may contain up to three hyphens, but 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 that precedes it (if there are fewer than three hyphens, there may or may not be a hyphen between the checksum digit and the digit that precedes it). So, for the purposes of this problem, the following are valid $\mbox{ISBN-10s}$:
$$
039428013\textrm{-X} \\
0\textrm{-}39\textrm{-}428013\textrm{X} \\
3\textrm{-}540\textrm{-}42580\textrm{-}2 \\
3540425802
$$
And the following are invalid $\mbox{ISBN-10s}$ (the first two because of a hyphen-placement error, the last because it 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
$$
How do you convert an $\mbox{ISBN-10}$ to an $\mbox{ISBN-13}$? Simply (i)prepend the three digits $978$, (ii)remove the old checksum digit, and (iii)append a new checksum digit as determined by the $\mbox{ISBN-13}$ rule. To keep things simple, maintain the positions of any existing hyphens, and follow the prepended $978$ with a hyphen.

The first line of input contains an integer, $T$ $(1 \leq T \leq 25)$, the number of (possibly invalid) $\mbox{ISBN-10s}$ to process. This is followed by $T$ lines, each of which contains a nonempty string of length between $10$ and $13$, inclusive. Each character is either a $\textrm{base-}10$ digit (${0}$ to ${9}$), a hyphen (${-}$), or ${X}$ (capital X).

For each test case, if the candidate $\mbox{ISBN-10}$ is not valid according to the details given above, output a line containing invalid. Otherwise, output a line containing the corresponding $\mbox{ISBN-13}$.