Bình Minh đang rất hứng thú với làm game. Anh Ta có dự định làm một game trong kỳ nghỉ hè này và quyết định làm sudoku.

Sudoku là một trò chơi câu đố sắp xếp chữ số dựa trên logic theo tổ hợp. Mục tiêu của trò chơi là điền các chữ số vào một lưới \(9 × 9\) sao cho mỗi cột, mỗi hàng, và mỗi phần trong số chín lưới con \(3 × 3\) cấu tạo nên lưới chính đều chứa tất cả các chữ số từ 1 tới 9. Cách đặt câu đố là cung cấp một lưới đã được hoàn thành một phần và người chơi phải điền các ô số còn lại sao cho thoả mãn điều kiện trên.

Bình Minh muốn làm được game này, anh ta phải tạo được ra câu đố đã. Các bạn hãy giúp Minh kiểm tra xem anh ta ra câu đố có đúng luật không.

Đầu vào:

• Dòng đầu tiên chứa 1 số nguyên n là số lượng câu đố Minh tạo ra.
• Các dòng tiếp theo được chia theo từng khối, mỗi khối cách nhau bởi 1 dòng, mỗi khối có 9 dòng, mỗi dòng có 9 số cách nhau bởi một dấu cách là các số của sudoku, nếu ô nào chưa được mở thì có giá trị là 0.

Đầu ra:

Gồm n dòng, nếu khối câu đố nào đúng luật thì in chữ true, khối nào sai luật thì in chữ false.

Ví dụ:

Input

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

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

Output

true
false

Giải thích:

ở khối game thứ 2, ta thấy cột 2 có 2 số 1 nên không thoả mãn là 1 đề bài của sudoku.

(Đề bài Sudoku do bạn Dương Anh Tú đóng góp).