FullHouse Dev và Cửa Hàng Thú Cưng

Bối cảnh

FullHouse Dev đi đến một cửa hàng thú cưng. Cửa hàng này có tổng cộng \(N\) con thú, trong đó con thú thứ \(i\) có loại \(A_i\).

Yêu cầu

FullHouse Dev quyết định mua một số con thú trong số \(N\) con thú này. Phần còn lại của các con thú sẽ được mua bởi một khách hàng khác sau khi FullHouse Dev đã mua xong.

Hãy xác định xem liệu có thể chia số thú sao cho FullHouse Dev và khách hàng khác sẽ có đúng cùng một đa tập hợp (multiset) các con thú hay không.

Input

• Dòng đầu tiên chứa một số nguyên \(T\), số lượng bộ test.
• Mỗi bộ test bao gồm nhiều dòng:
  • Dòng đầu tiên chứa số nguyên \(N\) — số lượng thú cưng trong cửa hàng.
  • Dòng tiếp theo chứa \(N\) số nguyên, là loại của mỗi con thú.

Output

• Với mỗi bộ test, in ra một dòng chứa "YES" nếu có thể chia các con thú thành hai phần với cùng một đa tập hợp, và "NO" nếu không thể.

Ràng buộc

• \(1 \leq T \leq 1000\)
• \(1 \leq N \leq 10^5\)
• \(1 \leq A_i \leq 100\)
• Tổng số \(N\) của tất cả các bộ test không vượt quá \(2 \cdot 10^5\).

Ví dụ 1

Input

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

Output

NO
YES
NO
YES

Giải thích ví dụ

• Test case 1: Có 4 trường hợp có thể xảy ra:

  • FullHouse Dev không mua con nào: khách hàng khác sẽ mua tất cả các con thú và có 3 con thú loại 4.
  • FullHouse Dev mua 1 con thú loại 4: khách hàng khác sẽ mua 2 con thú loại 4 còn lại.
  • FullHouse Dev mua 2 con thú loại 4: khách hàng khác sẽ mua 1 con thú loại 4 còn lại.
  • FullHouse Dev mua cả 3 con thú loại 4: khách hàng khác không mua con nào.
  • Trong mọi trường hợp, FullHouse Dev và khách hàng khác không thể có cùng đa tập hợp thú.

• Test case 2: Nếu FullHouse Dev mua các con thú số 1 và 2, có loại 2 và 3 tương ứng, khách hàng khác sẽ mua các con thú số 3 và 4, có loại 3 và 2 tương ứng. Như vậy, cả hai đều có 1 con thú loại 2 và 1 con thú loại 3.

• Test case 3: Có thể chứng minh rằng không thể chia số thú sao cho FullHouse Dev và khách hàng khác có cùng một đa tập hợp thú trong bất kỳ trường hợp nào.

• Test case 4: Nếu FullHouse Dev mua các con thú số 1, 2 và 5, có loại 5, 5 và 1 tương ứng, khách hàng khác sẽ mua các con thú số 3, 4 và 6, có loại 1, 5 và 5 tương ứng. Như vậy, cả hai đều có 1 con thú loại 1 và 2 con thú loại 5.

Thông tin học tập

• Buổi: B09
• Concepts: frequency arrays, bounded values
• Giới hạn kiến thức: B01-B09
• Time limit: 2 seconds
• Memory limit: 64 MB
• Point: 15