Sudoku Puzzle Validator

You are given one or more Sudoku puzzles. A Sudoku puzzle is a 9x9 grid and is valid if each row, every column, and each $3\times3$ sub-grid contains no duplicate digits (ignoring the placeholder character .). This problem asks you to verify the correctness of each Sudoku board.

Read the puzzle(s) from standard input and output the result for each puzzle: output Valid if the board is a valid configuration; otherwise, output Invalid.

inputFormat

The first line contains an integer T representing the number of Sudoku puzzles. Each puzzle consists of 9 subsequent lines, each line having exactly 9 characters (digits 1-9 or . for empty cells) representing one row of the board.

outputFormat

For each puzzle, print a single line containing either Valid or Invalid (without quotes) based on whether the puzzle is a valid Sudoku configuration.

1
53..7....
6..195...
.98....6.
8...6...3
4..8.3..1
7...2...6
.6....28.
...419..5
....8..79

Valid