Credit Card Validation

Interview

Time limit1sMemory limit128 MB

Summary

For each 16-digit card number, apply the Luhn checksum (double every second digit from the right, sum digits) and print T if the total is divisible by 10, else F.

Level: Easy2 of 10
Topics: Implementation, String, Math
Solved: No attempts yet

Problem

A credit card number has 16 digits. The digits look arbitrary, but they carry a rule that checks whether the number was entered correctly. That rule is the Luhn formula, and it works like this.

Count the digits from the rightmost one as position 1, position 2, and so on. Leave every digit in an odd position unchanged, and double every digit in an even position.
If a doubled value is 10 or more, replace it with the sum of its own digits.
Add up the 16 values obtained this way.
If the sum is divisible by 10, the number is valid. Otherwise the number is invalid.

You are given several credit card numbers. Decide whether each one is valid.

Input

The first line contains the number of test cases $T$ ( $1 \le T \le 1000$ ).

Each of the next $T$ lines contains one credit card number. Every number has exactly 16 digits, and its first digit may be 0.

Output

For each credit card number, print T if it is valid and F if it is not, one per line.

Examples4

Example 1

Input

3
2720992711828767
3444063910462763
6011733895106094

Expected output

T
F
T

Example 2
Input
```
1
0000000000000000
```
Expected output
```
T
```
Example 3
Input
```
1
9999999999999999
```
Expected output
```
F
```

Example 4

Input

2
0000000000000091
0000000000000019

Expected output

T
F