D - Hoverdia Eighteen

Hoverdia Eighteen is a number puzzle game similar to Sudoku, which gets its name from the restrictions placed on the puzzle in horizontal, vertical, and diagonal directions. The game is played on an eight-by-eight grid. The game has two rules:

1. Each row and column must contain the numbers one through eight, inclusive, with no duplicates.
2. Each of the four-by-four quarters of the puzzle must contain numbers such that the sum of any row, column, or diagonal is eighteen.

Write a program to determine the validity of a proposed solution to this game.

8	7	2	1	5	3	6	4
3	2	7	6	4	8	1	5
1	4	5	8	2	6	3	7
6	5	4	3	7	1	8	2
7	8	1	2	3	4	5	6
4	1	8	5	6	7	2	3
5	6	3	4	1	2	7	8
2	3	6	7	8	5	4	1

Input

Input will consist of a number of test cases, t, followed by a definition of each test case. Each test case consists of a line containing the puzzle name (up to 80 printable characters) and is followed by 8 lines, each containing 8 digits separated by space(s). The digits range from 1-8.

Output

Output a line for each test case, containing the puzzle name followed by “: ” and the word “valid” or “invalid”. Output “valid” if the puzzle satisfies the rules of an Eighteen puzzle. Output “invalid” if the puzzle violates the Eighteen puzzle rules.

Sample Input

2
 PUZZLE ONE
 8 7 2 1 5 3 6 4
 3 2 7 6 4 8 1 5
 1 4 5 8 2 6 3 7
 6 5 4 3 7 1 8 2
 7 8 1 2 3 4 5 6
 4 1 8 5 6 7 2 3
 5 6 3 4 1 2 7 8
 2 3 6 7 8 5 4 1
 PUZZLE TWO
 1 7 2 1 5 3 6 4
 3 2 7 6 4 5 1 8
 8 4 5 8 2 6 3 7
 6 5 4 3 5 1 8 2
 7 8 1 2 3 4 5 6
 4 1 8 5 6 7 2 3
 8 6 3 4 1 2 7 5
 2 3 6 5 7 8 4 1

Sample Output

PUZZLE ONE: valid
 PUZZLE TWO: invalid