IBAN checksum inspector

A payroll platform pays freelancers across Europe, the Gulf and South Asia. A mistyped IBAN means a lost transfer, so the platform runs the standard IBAN checksum before sending money.

Validation steps for one IBAN: remove all spaces and convert to upper case (this is the compact form). It is INVALID unless all of these hold: it uses only letters A-Z and digits; its length is 15 to 34; its first two characters are letters and the next two are digits. Then move the first four characters to the end, replace each letter by a number (A=10, B=11, ... Z=35) and read the whole thing as one big integer. The IBAN is VALID when that integer leaves remainder 1 when divided by 97. (Country-specific lengths are not checked.)

Task: the first line is N. Each of the next N lines holds one IBAN as typed. For each, print the compact form, a colon, a space and VALID or INVALID, for example GB82WEST12345698765432: VALID.

Sample tests

Input

3
GB82 WEST 1234 5698 7654 32
GB82 WEST 1234 5698 7654 33
de89 3704 0044 0532 0130 00

Expected output

GB82WEST12345698765432: VALID
GB82WEST12345698765433: INVALID
DE89370400440532013000: VALID

Input

2
PK36 SCBL 0000 0011 2345 6702
AE07 0331 2345 6789 0123 456

Expected output

PK36SCBL0000001123456702: VALID
AE070331234567890123456: VALID

Your answer is also checked against 2 hidden tests.