Polygon

Cho một ma trận vuông cạnh $n$ ban đầu toàn ký tự $0$. Phía trên mỗi cột (cột $j$) đặt một khẩu súng bắn xuống dưới, và bên trái mỗi hàng (hàng $i$) đặt một khẩu súng bắn sang phải — tổng cộng $2n$ khẩu.

Mỗi lần bắn, viên đạn là ký tự $1$. Tại một thời điểm chỉ có một khẩu bắn. Viên đạn bay theo hướng của khẩu súng (từ trên xuống nếu là súng cột, từ trái sang phải nếu là súng hàng) cho đến khi:

• chạm vào biên đối diện của ma trận, hoặc
• chạm vào một ô đã chứa ký tự $1$.

Khi đó nó dừng lại và chiếm ô liền trước vị trí va chạm. Mỗi khẩu súng có thể bắn tùy ý số lần.

Cho ma trận kết quả gồm ký tự $0$ và $1$. Hãy xác định xem có tồn tại một chuỗi phát bắn nào đó dẫn đến ma trận này hay không.

Dữ liệu vào

• Dòng đầu chứa số nguyên $t$ — số test ($1\le t\le 1000$).
• Mỗi test bắt đầu bằng dòng chứa số nguyên $n$ ($1\le n\le 50$) — kích thước ma trận. Tiếp theo là $n$ dòng, mỗi dòng gồm $n$ ký tự $0$ hoặc $1$, mô tả ma trận sau quá trình bắn.
• Tổng diện tích của các ma trận trong một test không vượt quá ${10}^5$.

Dữ liệu ra

Với mỗi test, in ra YES nếu tồn tại chuỗi phát bắn dẫn tới ma trận đã cho, ngược lại in NO. Các chữ cái có thể viết hoa hoặc thường tuỳ ý.

Ràng buộc

• $1\le t\le 1000$
• $1\le n\le 50$
• Tổng $n^2$ qua tất cả các test không vượt quá ${10}^5$.

Ví dụ