# FBI Universal Control Numbers

The **FBI** has recently changed its
*Universal Control Numbers (UCN)* for identifying
individuals who are in the FBI’s fingerprint database to an
eight digit base $27$
value with a ninth check digit. The digits used are:

0123456789ACDEFHJKLMNPRTVWX

Some letters are not used because of possible confusion with other digits:

B->8, G->C, I->1, O->0, Q->0, S->5, U->V, Y->V, Z->2

The check digit is computed as:

(2*D1 + 4*D2 + 5*D3 + 7*D4 + 8*D5 + 10*D6 + 11*D7 + 13*D8) mod 27

Where `Dn` is the $n^{\text {th}}$ digit from the
left.

This choice of *check* digit detects any single digit
error and any error transposing an adjacent pair of the
original eight digits.

For this problem, you will write a program to parse a
*UCN* input by a user. Your program should accept
decimal digits and *any* capital letter as digits. If
any of the *confusing* letters appear in the input, you
should replace them with the corresponding valid digit as
listed above. Your program should compute the correct
*check* digit and compare it to the entered check digit.
The input is rejected if they do not match otherwise the
decimal (base $10$) value
corresponding to the first eight digits is returned.

## Input

The first line of input contains a single decimal integer $P$, ($1 \le P \le 10\, 000$), which is the number of data sets that follow. Each data set should be processed identically and independently. Each data set consists of a single line of input. It contains the data set number, $K$, followed by a single space, followed by $9$ decimal digits or capital (alphabetic) characters.

## Output

For each data set there is one line of output. The single
output line consists of the data set number, $K$, followed by a single space
followed by the string “`Invalid`”
(without the quotes) or the decimal value corresponding to the
first eight digits.

Sample Input 1 | Sample Output 1 |
---|---|

3 1 12345678A 2 12435678A 3 12355678A |
1 11280469652 2 Invalid 3 Invalid |