Product Code Validator

You are given a list of product codes. A valid product code adheres to the following rules:

• It starts with two uppercase letters (A-Z).
• It is followed by exactly eight digits (0-9), i.e. the numerical part has length 8.
• It ends with two lowercase letters (a-z).

Your task is to write a program that reads an integer T from the standard input, followed by T product codes (one per line). For each product code, print Valid if it meets all the criteria, or Invalid otherwise.

In mathematical terms, a valid product code matches the regular expression in LaTeX format as follows:

$$ ^[A-Z]\{2\}\d\{8\}[a-z]\{2\}$ $$

inputFormat

The first line of input contains a single integer T (0 \le T \le 10^5), representing the number of product codes to validate. The following T lines each contain a product code string.

outputFormat

For each product code, output a single line containing either Valid if the code meets all the criteria, or Invalid otherwise.

## sample

1
AB12345678cd

Valid

</p>