Migrated from Lutece 267 Check a Sudoku

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Sudoku is a puzzle of a $9 \times 9$ grid made up of $3 \times 3$ subgrids (called regions).Some cells already contain numbers, known as givens. The goal is to fill in the empty cells, one number in each, so that each column, row, and region contains the numbers $1$ through $9$ exactly once. Each number in the solution therefore occurs only once in each of three "directions, hence the single numbers implied by the puzzle's title.

The attraction of the puzzle is that the completion rules are simple, yet the line of reasoning required to reach the completion may be difficult. Published puzzles often are ranked in terms of difficulty. This also may be expressed by giving an estimated solution time. While, generally speaking, the greater the number of givens, the easier the solution, the opposite is not necessarily true. The true difficulty of the puzzle depends upon how easy it is to logically determine subsequent numbers.

TheBeet is fond of this game, he has solve lots of sudokus. But one day, when he check the puzzles he had solve before, some of them does not look correct. Now TheBeet is busy with his homework. As one of the best programmer in XMU, could you kind enough to help TheBeet to check the puzzles?

Input

The first line of the input contains one integer $n (n < 20)$, which represents the number of test cases.

Each test case contains $9$ lines, each line contains $9$ integers, which represent the answer to the puzzle you should check.

There is a blank line after each test case.

Output

For each test case, output Case #: on the first line, # is the number of the test case; then you should outputYes! (without quotes) if the answer is correct, otherwise you should output No!.

Samples

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

Case 1:
Yes!

Resources

厦门大学第四届程序设计竞赛 现场决赛