Remember that a Sudoku is a game that consists of completing a 9 × 9 grid with numbers between 1 and 9, so that the final result has not repeated numbers in the same row, column or 3 × 3 submatrix. For example, this is a Sudoku and its solution:

unit=0.6cm
linewidth=0.1pt
(9,9)
[linewidth=1.25pt](0,0)(0,9)
(1,0)(1,9)
(2,0)(2,9)
[linewidth=1.25pt](3,0)(3,9)
(4,0)(4,9)
(5,0)(5,9)
[linewidth=1.25pt](6,0)(6,9)
(7,0)(7,9)
(8,0)(8,9)
[linewidth=1.25pt](9,0)(9,9)

[linewidth=1.25pt](0,0)(9,0) (0,1)(9,1) (0,2)(9,2) [linewidth=1.25pt](0,3)(9,3) (0,4)(9,4) (0,5)(9,5) [linewidth=1.25pt](0,6)(9,6) (0,7)(9,7) (0,8)(9,8) [linewidth=1.25pt](0,9)(9,9)

[c](0.5,0.5)4 [c](2.5,0.5)5 [c](3.5,0.5)6

[c](1.5,1.5)2 [c](2.5,1.5)9 [c](3.5,1.5)1

[c](4.5,2.5)7 [c](5.5,2.5)5 [c](8.5,2.5)8

[c](2.5,3.5)6 [c](3.5,3.5)4 [c](4.5,3.5)2

[c](1.5,4.5)4 [c](2.5,4.5)8 [c](6.5,4.5)5 [c](7.5,4.5)6

[c](4.5,5.5)6 [c](5.5,5.5)1 [c](6.5,5.5)8

[c](0.5,6.5)1 [c](3.5,6.5)9 [c](4.5,6.5)3

[c](5.5,7.5)6 [c](6.5,7.5)4 [c](7.5,7.5)5

[c](5.5,8.5)2 [c](6.5,8.5)3 [c](8.5,8.5)7

(9,9) [linewidth=1.25pt](0,0)(0,9) (1,0)(1,9) (2,0)(2,9) [linewidth=1.25pt](3,0)(3,9) (4,0)(4,9) (5,0)(5,9) [linewidth=1.25pt](6,0)(6,9) (7,0)(7,9) (8,0)(8,9) [linewidth=1.25pt](9,0)(9,9)

[linewidth=1.25pt](0,0)(9,0) (0,1)(9,1) (0,2)(9,2) [linewidth=1.25pt](0,3)(9,3) (0,4)(9,4) (0,5)(9,5) [linewidth=1.25pt](0,6)(9,6) (0,7)(9,7) (0,8)(9,8) [linewidth=1.25pt](0,9)(9,9)

[c](0.5,0.5)4 [c](1.5,0.5)7 [c](2.5,0.5)5 [c](3.5,0.5)6 [c](4.5,0.5)8 [c](5.5,0.5)9 [c](6.5,0.5)1 [c](7.5,0.5)3 [c](8.5,0.5)2

[c](0,1) [c](0.5,0.5)9 [c](1.5,0.5)2 [c](2.5,0.5)9 [c](3.5,0.5)1 [c](4.5,0.5)4 [c](5.5,0.5)3 [c](6.5,0.5)6 [c](7.5,0.5)7 [c](8.5,0.5)5

[c](0,2) [c](0.5,0.5)6 [c](1.5,0.5)3 [c](2.5,0.5)1 [c](3.5,0.5)2 [c](4.5,0.5)7 [c](5.5,0.5)5 [c](6.5,0.5)9 [c](7.5,0.5)4 [c](8.5,0.5)8

[c](0,3) [c](0.5,0.5)5 [c](1.5,0.5)1 [c](2.5,0.5)6 [c](3.5,0.5)4 [c](4.5,0.5)2 [c](5.5,0.5)8 [c](6.5,0.5)7 [c](7.5,0.5)9 [c](8.5,0.5)3

[c](0,4) [c](0.5,0.5)2 [c](1.5,0.5)4 [c](2.5,0.5)8 [c](3.5,0.5)3 [c](4.5,0.5)9 [c](5.5,0.5)7 [c](6.5,0.5)5 [c](7.5,0.5)6 [c](8.5,0.5)1

[c](0,5) [c](0.5,0.5)7 [c](1.5,0.5)9 [c](2.5,0.5)3 [c](3.5,0.5)5 [c](4.5,0.5)6 [c](5.5,0.5)1 [c](6.5,0.5)8 [c](7.5,0.5)2 [c](8.5,0.5)4

[c](0,6) [c](0.5,0.5)1 [c](1.5,0.5)5 [c](2.5,0.5)7 [c](3.5,0.5)9 [c](4.5,0.5)3 [c](5.5,0.5)4 [c](6.5,0.5)2 [c](7.5,0.5)8 [c](8.5,0.5)6

[c](0,7) [c](0.5,0.5)3 [c](1.5,0.5)8 [c](2.5,0.5)2 [c](3.5,0.5)7 [c](4.5,0.5)1 [c](5.5,0.5)6 [c](6.5,0.5)4 [c](7.5,0.5)5 [c](8.5,0.5)9

[c](0,8) [c](0.5,0.5)9 [c](1.5,0.5)6 [c](2.5,0.5)4 [c](3.5,0.5)8 [c](4.5,0.5)5 [c](5.5,0.5)2 [c](6.5,0.5)3 [c](7.5,0.5)1 [c](8.5,0.5)7

In this problem we do not ask you to solve any Sudoku, just to check that every given matrix can be the solution of a Sudoku.

Input

Input consists of a number n, followed by n cases. Every case has 9 rows, each one with 9 numbers between 1 and 9.

Output

For every case, print “yes” or “no” depending on whether the given matrix follows the rules of the solutions of Sudokus.

Public test cases

**Input**

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

**Output**

yes no

Information

- Author
- Salvador Roura
- Language
- English
- Translator
- Salvador Roura
- Original language
- Catalan
- Other languages
- Catalan
- Official solutions
- C++ Python
- User solutions
- C++ Python