FBI Universal Control Numbers

The FBI identifies a person in its fingerprint database with a Universal Control Number (UCN): eight base 27 digits followed by a ninth check digit. The 27 digit characters are:

0123456789ACDEFHJKLMNPRTVWX

The remaining letters are left out because they are easy to confuse with other digits. When one of them appears in the input, replace it with the digit shown here:

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

The check digit is

$(2 D_1 + 4 D_2 + 5 D_3 + 7 D_4 + 8 D_5 + 10 D_6 + 11 D_7 + 13 D_8) \bmod 27$

where $D_n$ is the nth digit from the left. This check digit catches any single wrong digit and any swap of an adjacent pair among the first eight digits.

Write a program that parses a UCN typed by a user. Accept decimal digits and any capital letter as digits. Replace every confusing letter, including the ninth character, according to the table above, then compute the correct check digit and compare it with the entered check digit. If the two differ, reject the input. Otherwise print the decimal (base 10) value of the first eight digits.

The first line contains one integer $P$ ($1 \le P \le 10000$), the number of data sets.

Each of the next $P$ lines holds one data set: the data set number $K$, one space, then nine characters, each a decimal digit or a capital letter.

Data sets are independent and are all processed the same way.

Print one line per data set: the data set number $K$, one space, then Invalid if the check digit does not match, or the decimal value of the first eight digits if it does.