Problem 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