These days, it has become commonplace to make purchases over the internet using a credit card. However, because credit card numbers are relatively long, it is easy to make a mistake while typing them in. In order to quickly identify errors like typos, most e-commerce websites use a checksum algorithm to verify credit card numbers.
One popular checksum algorithm is the Luhn algorithm, which can detect any single-digit error as well as many common multiple-digit errors:
For example, using the number 5181 2710 9900 0012:
For this problem, you must write a program that checks the validity of credit card numbers according to the Luhn algorithm.
The input begins with a number N on a single line, followed by N lines each containing a single credit card number. Each credit card number consists of 16 decimal digits in groups of four separated by single spaces.
The output consists of one line for each input credit card number. If the credit card number is valid, this line consists of the string "Valid", otherwise it reads "Invalid".
2 5181 2710 9900 0012 5181 2710 9900 0017
Invalid Valid