Vào giờ giải lao, các thành viên đội OLP Tin học UTC đang bàn luận về giá trị tiền tệ của các quốc gia.

Giá trị tiền của các quốc gia có thể bằng nhau hoặc hơn kém nhau. Phương là một người rất yêu thích kinh doanh, cô liền nảy ra trong đầu một ý tưởng kinh doanh tiền tệ, Với tư duy của một thành viên kì cựu trong đội tuyển, Phương liền quy ý tưởng này về một bài toán như sau:

Cho biết cách quy đổi đơn vị tiền tệ giữa các quốc gia, Hãy chỉ ra xem liệu ta có thể kiếm tiền bằng việc thực hiện một số thao tác quy đổi tiền giữa các quốc gia hay không.

Câu hỏi cuối cùng đặt ra là:

Xuất phát từ tiền tệ ở nước bất kì, sau các thao tác quy đổi và quay trở lại tiền tệ ở nước ban đầu, liệu Phương có thể có lượng tiền lớn hơn ban đầu ?

Các bạn hãy giúp Phương viết chương trình trả lời câu hỏi này nhé

Input

Dòng đầu tiên là số T (1 <= T <= 5) là số lượng testcase.

Các dòng tiếp theo mô tả các test case.

Với mỗi testcase:

• Dòng đầu tiên gồm một số nguyên duy nhất n mô tả số quốc gia. \((1 <= n <= 14)\)
• n dòng tiếp theo mô tả tỉ lệ chuyển đổi giữa n quốc gia trong một ma trận a có kích thước n * n:

Tại dòng thứ i \((1 <= i <= n)\) bao gồm n số thực, đánh số từ 1 dến n, số thứ j: a[i][j] \((1 <= j <= n)\) mô tả tỉ lệ chuyển đổi tiền tệ giữa quốc gia thứ i và quốc gia thứ j. Nếu i = j thì a[i][j] = 1 vì cùng một quốc gia. \((0.001 <= a[i][j] <= 1000).\)

Output

Với mỗi testcase in ra trên một dòng duy nhất là "YES" nếu lượng tiền lớn hơn ban đầu sau các thao tác quy đổi. NGược lại in ra "NO". (không tính dấu ngoặc kép)

Giải thích sample test:

Test1: Bắt đầu từ 1$ tiền tệ của quốc gia 1, ta có thể đổi được 0.5 $ tiền tệ của quốc gia thứ 2, sau đó, từ 0.5$ ta lại đổi được 0.25$ sang tiền tệ ở quốc gia thứ 3. Cuối cùng từ 0.25$ ta đổi được 0.9875$ tiền tệ quốc gia 1 ( ban đầu). Đây là ví dụ của một chuỗi các thao tác chuyển đổi hợp lệ. Trong ví dụ này, không có cách nào chuyển đổi được hơn số tiền ban đầu. In ra NO.

Test2: Tương tự như test1, tuy nhiên tại bước chuyển từ tiền tệ tại quốc gia thứ 3 về quốc gia 1, ta quy đổi được 1.0125$ lớn hơn 1$ ban đầu. in ra YES

Ví dụ

Input

2
3
1 0.5 0.2 
1.8 1 0.5 
3.95 1.2 1
3
1 0.5 0.2 
1.8 1 0.5 
4.05 1.2 1

Output

NO
YES