Ông Sắc là một doanh nhân đại tài, ông đã xây dựng nên sự nghiệp của ông từ con số \(1\). Trong một khóa dạy kinh doanh, ông đã đưa ra bài toán cho những học trò của mình dựa trên trải nghiệm của mình:

Dãy \(a\) ban đầu chỉ có duy nhất phần tử \(1\). Chọn dãy con từ dãy \(a\) và chèn vào dãy \(a\) tổng của các phần tử trong dãy con ấy. Nói cách khác chọn \(k\) chỉ số khác nhau \(i_1, i_2, \dots, i_k\) và chèn vào dãy \(a\) một giá trị \(a_{i_1} + a_{i_2} + \dots + a_{i_k}\).

Cho trước một dãy \(b\). Hỏi từ dãy \(a\) có tạo được nên dãy \(b\) không?

Input

• Dòng đầu tiên chứa \(t\) là số lượng bộ dữ liệu khác nhau (\(1 \le t \le 20\)).
• \(t\) nhóm sau, mỗi nhóm gồm \(2\) dòng:
  • Dòng đầu chứa số nguyên dương \(n\) (\(n \le 10^5\)).
  • Dòng tiếp theo chứa \(n\) số \(b_1, b_2, \dots, b_n\) (\(b_i \le 2\cdot 10^5\)).

Output

• In ra YES nếu đúng yêu cầu đề bài, ngược lại in ra NO.

Example

5
1
1
4
1 1 1 1
3
2 4 6
4
1 5 3 1
5
1 3 1 1 5

YES
YES
NO
NO
YES

Scoring

• Subtask 1 (\(50\%\) số điểm): \(n \le 10^3\), \(b_i \le 10^3\).
• Subtask 2 (\(50\%\) số điểm): Không có ràng buộc gì thêm.