A product-code scheme defines an 8-character code: the first 7 characters must all be digits 0-9, and the 8th character (the check character) must be either a digit or the uppercase letter X (representing the value 10).

The correct check character is computed from the first 7 digits d1 d2 ... d7 (left to right) using the weights 8 7 6 5 4 3 2 respectively: let total = 8*d1 + 7*d2 + 6*d3 + 5*d4 + 4*d5 + 3*d6 + 2*d7, and check = (11 - (total mod 11)) mod 11. If check equals 10, the correct check character is X; otherwise it is the single digit check.

Given n codes, one per line, print VALID if a code is exactly 8 characters long, its first 7 characters are all digits, its 8th character is a digit or X, AND its 8th character equals the computed check character; otherwise print INVALID.

Input format

Line 1: an integer n. Lines 2..n+1: one code per line (each line's length may vary; it need not be exactly 8 characters).

Output format

n lines: VALID or INVALID for each code, in order.

Constraints

• 1 ≤ n ≤ 50
• 0 ≤ length of each code ≤ 12
• each code consists of ASCII letters and digits only

2
12345679
12345670

VALID
INVALID

1
123

INVALID