Tại trung tâm nghiên cứu vô tuyến, các chuyên gia đang thử nghiệm một giao thức truyền tin mật mã mới. Mỗi thông điệp được mã hóa thành một chuỗi gồm \(n\) tín hiệu rời rạc, tín hiệu thứ \(j\) có cường độ là một số nguyên dương \(a_j\).

Để giải mã được thông điệp, hệ thống cần tìm cách đồng bộ hóa chuỗi tín hiệu này. Quá trình đồng bộ hóa thành công nếu hệ thống có thể đảo lộn thứ tự các tín hiệu trong chuỗi ban đầu để tạo ra một cấu hình mới, sao cho tồn tại một điểm cắt \(i\) (\(1 \le i < n\)) chia chuỗi thành hai phần thỏa mãn tính chất:

• Ngưỡng năng lượng tối thiểu của phần đầu tiên (từ vị trí \(1\) đến \(i\)) phải bằng chính xác tần số cơ bản (ước chung lớn nhất) của phần thứ hai (từ vị trí \(i + 1\) đến \(n\)).

Nói cách khác, từ dãy \(a_1, a_2, \dots, a_n\) ban đầu, cần kiểm tra xem có tồn tại một hoán vị của dãy và một chỉ số \(i\) sao cho:

Yêu cầu: Cho trước \(T\) bộ dữ liệu thử nghiệm, mỗi bộ chứa \(n\) cường độ tín hiệu \(a_1, a_2, \dots, a_n\). Với mỗi bộ dữ liệu, hãy xác định xem có tồn tại cách đảo lộn thứ tự thỏa mãn điều kiện đồng bộ khóa hay không.

Input

• Dòng đầu tiên chứa số nguyên dương \(T\) (\(T \le 5\)) là số lượng bộ test.
• Tiếp theo là \(T\) nhóm dòng, mỗi nhóm tương ứng với một bộ test có cấu trúc như sau:
  • Dòng thứ nhất chứa số nguyên dương \(n\) là số lượng tín hiệu.
  • Dòng thứ hai chứa \(n\) số nguyên dương \(a_1, a_2, \dots, a_n\) (\(a_j \le 10^{12}\)), các số được ghi cách nhau bởi khoảng trắng.

Output

• Gồm \(T\) dòng, dòng thứ \(k\) ghi đáp án cho bộ test thứ \(k\). In ra YES nếu tồn tại cách hoán vị thỏa mãn yêu cầu, ngược lại in ra NO.

Example

2
3
6 4 2
3
3 5 7

YES
NO

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n \le 10\).
• Subtask \(2\) (\(30\%\) số điểm): \(10 < n \le 100\).
• Subtask \(3\) (\(40\%\) số điểm): \(100 < n \le 10^6\) (Tổng \(n\) trong tất cả các testcase không vượt quá \(10^6\)).