Task 3. Luhn Algorithm

Available Marks: 11

The algorithm devised by Hans Peter Luhn in 1954 to determine whether sequences of digits have (probably) been typed without error is still used to this day for things like credit card number validation. It works like this: to validate a sequence of digits (each in the range 0 to 9) that has been suitably encoded,

1. Counting from the right, add the digits in odd positions (last, third last, etc).
2. Double each digit in an even position. If the result is greater than 9, add the two digits together. Add the resulting even-position values.
3. Add the odd and even sums. If the overall sum is not a multiple of 10, the sequence is invalid.

For example, if the encoded sequence is 71368054, the calculation gives a final sum of 30, which is indeed a multiple of 10 (even positions are shaded): 

However if, say, the adjacent digits 6 and 8 were accidentally swapped, the sum is no longer divisible by 10: 

The Luhn algorithm can be used to add a check digit to an account number so that common typing errors can be detected. The check digit, when determined, is appended to the original number so it's in an odd position and won't be doubled. You can use this fact to devise a way of generating the full Luhn code.

Your Task

Write a program that can either validate a number that has been encoded for Luhn validation, or generate the Luhn code for a digit sequence. Each line of input contains either a V (for validate) or E (for encode), a space, then a string of up to 20 digits. Leading zeros are ordinary digits. The number of data lines is on the first line of the input.

If the action is validate, display the number and then either the string " is valid" or the string " is INVALID" as appropriate. If the action is encode, display the encoded value, with is the original number with the calculated check digit appended to it, followed by the word " encoded".

Example

5
V 00000
V 71368054
V 0071368056
E 7136805
E 123456789

Output:

00000 is valid.
71368054 is valid.
0071368056 is INVALID.
71368054 encoded
1234567897 encoded

Marking Scheme

6 marks for correct validation and 5 for correct encoding.

Test Data

20
V 123
V 1234
V 4444444
V 987654321
V 1357924680
V 13579246805
V 13572946805
V 93450345330
V 09345034533
V 30934503453
V 32049509345969205438
E 123
E 9999
E 76543
E 893563
E 21388462
E 034234273
E 20394284834
E 9837982348977317
E 9823423894798723444