Hoverdia Board Validator

Hoverdia is a number puzzle like sudoku, getting its name from horizontal, vertical, and diagonal. The puzzle consists of a 8 x 8 grid where each row and column must contain all the numbers from 1 to 8 inclusively. The grid is further divided into 4 sub-puzzles of disjoint 4x4 boxes. Each row, column, and diagonal of the 4x4 boxes must add up to 18. The program will report the correctness of a given puzzle.

Input

The first line of input from the console contains the number of test cases t. Each test case consists of a line containing the puzzle name and is followed by 8 lines, each containing 8 digits separated by space(s). The digits range from 1-8. There is at least one test case and less than 1,000,000,000.

Output

Output one 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; otherwise, output invalid.

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