Phép nhân hai ma trận chỉ thực hiện được khi số cột của ma trận bên trái bằng số dòng của ma trận
bên phải. Nếu ma trận \(A\) có kích thước \(m\) x \(n\) và ma trận \(B\) có kích thước \(n\) x \(p\) , thì ma trận
tích C = \(A\) x \(B\) có kích thước \(m\) x \(p\) , phần tử đứng ở hàng thứ \(i\), cột thứ \(j\) xác định bởi:

\(c_{i,j} = a_{i,1}b_{1,j} + a_{i,2}b_{2,j} + \dots + a_{i,n}b_{n,j}\)

Phép nhân ma trận có các tính chất kết hợp: (\(A\) x \(B\)) x \(C\) = \(A\) x (\(B\) x \(C\))

Ví dụ:
\(A = \binom{0, 1}{1, 1}; A^2 = \binom{1, 1}{1, 2}; A^3 = \binom{1, 2}{2, 3}\)

Yêu cầu: Cho ma trận \(A\) kích thước \(n\) x \(n\) và ma trận B, hãy kiểm tra xem \(A^3\) có bằng hay \(B\) không?

Input

• Dòng thứ nhất chứa số nguyên dương \(T\) \((T \leq 20)\) là số lượng bộ dữ liệu;
• Tiếp theo là \(T\) nhóm dòng, mỗi nhóm dòng tương ứng với một bộ dữ liệu có dạng:
• Dòng đầu chứa số nguyên \(n\);
• \(n\) dòng tiếp theo, mỗi dòng chứa \(n\) số nguyên mô tả ma trận \(A\), các số có giá trị tuyệt đối không vượt quá 1000;
• \(n\) dòng tiếp theo, mỗi dòng chứa \(n\) số nguyên mô tả ma trận \(B\), các số có giá trị tuyệt đối không vượt quá 10^18.

Output

Ghi ra thiết bị ra chuẩn gồm \(T\) dòng, mỗi dòng là kết quả tương ứng với một bộ dữ liệu theo thứ tự xuất hiện trong file dữ liệu vào: ghi thông báo ‘YES’ nếu \(A^3 = B\) và ghi ‘NO’ trong trường hợp ngược lại.

Scoring

• Có \(50\)% số test ứng với \(50\)% số điểm của bài thỏa mãn: \(n \leq 10\);
• \(50\)% số test còn lại ứng với \(50\)% số điểm của bài thỏa mãn: \(n \leq 500\).

Example

2
2
0 1 
1 1
1 2
2 2
2
0 1 
1 1
1 2
2 3

NO
YES