You need to check whether a credit card number is valid or not. These credit card numbers must follow the Luhn algorithm, which is described as follows:

1. Double every other digit, starting from the first digit.
2. If doubling a digit results in a value greater than 9, subtract 9 from it (or sum its digits).
3. Sum all the digits (including the ones that were not doubled).
4. If the sum is a multiple of 10, it is a valid credit card number.

Input Specification

A sixteen digit number.

Output Specification

Output either "valid" or "invalid".

Sample Input

4539704354706391

Sample Output

valid

Explanation for Sample Output

This number is valid because it follows the described rules. The first step is to double every other digit, starting with the first digit. This means the first digit, third digit, fifth digit, etc. will be doubled. The following digits, in order, will be doubled: 4, 3, 7, 4, 5, 7, 6, and 9. So far, the digits of the number look like this (separated): 8, 5, 6, 9, 14, 0, 8, 3, 10, 4, 14, 0, 12, 3, 18, 1. Next, if any number here is greater than 9, subtract 9 from it, which results in the following digits: 8, 5, 6, 9, 5, 0, 8, 3, 1, 4, 5, 0, 3, 3, 9, 1. Then, add all of these numbers up to get a total of 70. Since 70 is a multiple of 10, this credit card number is valid.