A higher resolution is required to access the IDE

- 868

## Learning Opportunities

This puzzle can be solved using the following concepts. Practice using these concepts and improve your skills.

## Statement

## Goal

Most payment card numbers are 16 digits long. The leftmost 6 digits represent a unique identification number for the bank who has issued the card. The next 2 digits determine the type of the card (e.g., debit, credit, gift). Digits 9 to 15 are the serial number of the card, and the last digit is used as a control digit to verify whether the card number is valid. Hence, if somebody enters the card number incorrectly, there is a high chance that a payment software can easily determine it.Most cards use an algorithm invented by Hans Peter Luhn, a nice fellow from IBM. According to Luhn’s algorithm, you can determine if a credit card number is (syntactically) valid as follows:

**1.**Double every second digit from right to left. If this “doubling” results in a two-digit number, subtract 9 from it get a single digit.

**2.**Now add all single digit numbers from step

**1**.

**3.**Add all digits in the odd places from right to left in the credit card number.

**4.**Sum the results from steps

**2**&

**3**.

**5.**If the result from step

**4**is divisible by 10, the card number is valid; otherwise, it is invalid.

for example:

**Test 1:**

4556 7375 8689 9855

**1.**

5*2 9*2 8*2 8*2 7*2 7*2 5*2 4*2

10 18 16 16 14 14 10 8

1 9 7 7 5 5 1 8

**2.**

1+9+7+7+5+5+1+8=43

**3.**

5+8+9+6+5+3+6+5=47

**4.**

43+47=90

The number is valid

**Test 2:**

4024 0071 0902 2143

**1.**

4*2 2*2 0*2 0*2 7*2 0*2 2*2 4*2

8 4 0 0 14 0 4 8

8 4 0 0 5 0 4 8

**2.**

8+4+0+0+5+0+4+8=29

**3.**

3+1+2+9+1+0+4+0=20

**4.**

20+29=49

Therefore the number not valid.

So, validating credit card numbers isn’t hard, but it does get a bit tedious by hand.

Your task is to read several card numbers from the input, and determine whether each one is a valid card number or not.

Input

**Line 1**: An integer

`N`for the number of cards to verify.

**Next**: One line for each card to verify. Each test is consisting of four space-separated 4-digit strings.

`N`linesOutput

**: For each test case, output a line containing**

`N`linesConstraints

Example

Input

2 4556 7375 8689 9855 4024 0071 0902 2143

Output

YES NO

A higher resolution is required to access the IDE