Yaaaay, Haven't you heard the news? Bakaloria results are out! And Reem had very good grades. Finally she can go to IT college and pursue her childhood dream of becoming a great programmer.
Reem is very excited about her college, she already started learning programming. Today she was learning about a very well known problem, the 8-Queens problem (you never saw that coming, didn't you?) she has wrote a program to generate all the possible situations of the queens, but as a novice programmer she found it hard to check whether if these situations are valid. As usual you come to her rescue and offer to help with this hard task!
Now you are stuck with this task: Given the positions of 8 queens on a regular chess board, determine if this situation is valid.
A valid situation is a configuration of the 8 queens where no queen can strike any other queen.
On a standard 8 × 8 chess board, a queen can strike any other queen on it's row, column, or two diagonals.
The first line of input has one integer T the number of test cases your program must process.
Each of the next T lines contains the positions of 8 queens. A position of a queen is described as one character [A - H] (the column of the queen), followed by one number [1 - 8] (the row of the queen)
For example: "A4" represents a queen at the first column and the fourth row.
(see sample input for more details)
For each test case print one line containing the word _Valid_ if the configuration is valid, or _Invalid_ otherwise.
## Input
The first line of input has one integer T the number of test cases your program must process.Each of the next T lines contains the positions of 8 queens. A position of a queen is described as one character [A - H] (the column of the queen), followed by one number [1 - 8] (the row of the queen)For example: "A4" represents a queen at the first column and the fourth row.(see sample input for more details)
## Output
For each test case print one line containing the word _Valid_ if the configuration is valid, or _Invalid_ otherwise.
[samples]
**Definitions**
Let $ T \in \mathbb{Z} $ be the number of test cases.
For each test case $ k \in \{1, \dots, T\} $, let $ Q_k = \{ (c_i, r_i) \mid i \in \{1, \dots, 8\} \} $ be a set of 8 queen positions, where:
- $ c_i \in \{A, B, C, D, E, F, G, H\} $ denotes the column (mapped to $ x_i = c_i - A + 1 \in \{1, \dots, 8\} $),
- $ r_i \in \{1, 2, 3, 4, 5, 6, 7, 8\} $ denotes the row (1-indexed).
Thus, each queen is represented as a coordinate $ (x_i, y_i) \in \{1, \dots, 8\}^2 $, with $ x_i = \text{ord}(c_i) - \text{ord}('A') + 1 $, $ y_i = r_i $.
**Constraints**
1. $ 1 \le T \le \text{some bound} $ (implied by input size, not specified)
2. For each $ k $, the 8 positions in $ Q_k $ are given as 8 distinct strings of the form $ [A-H][1-8] $.
3. No assumption of distinctness is made — duplicates must be rejected.
**Objective**
For each test case $ k $, determine whether no two queens attack each other:
$$
\forall i, j \in \{1, \dots, 8\},\ i \ne j: \quad
\neg \left(
x_i = x_j \lor y_i = y_j \lor x_i - y_i = x_j - y_j \lor x_i + y_i = x_j + y_j
\right)
$$
Output "Valid" if the condition holds for all pairs; otherwise, output "Invalid".