Array with Odd Sum (Array with Odd Sum)

Nguồn: Codeforces

Phiên bản: Phước Hưng OJ Extended

Đề bài

Với mỗi test, cho mảng $a$ gồm $n$ số nguyên dương. Một thao tác chọn hai chỉ số khác nhau $i\ne j$ và thực hiện

Có thể thực hiện thao tác bao nhiêu lần tùy ý, kể cả $0$ lần. Hãy xác định liệu có thể thu được một mảng có tổng phần tử là số lẻ hay không.

Nếu tổng ban đầu đã lẻ thì câu trả lời hiển nhiên là YES. Nếu tổng ban đầu chẵn, một phép gán chỉ có thể đổi parity của tổng khi mảng có đồng thời ít nhất một số chẵn và một số lẻ.

Input

Dòng đầu chứa $t$. Mỗi test gồm một dòng $n$, sau đó một dòng chứa $n$ số $a_i$.

Output

Với mỗi test, in YES nếu có thể thu được tổng lẻ, ngược lại in NO.

Subtask

Subtask 1 (20 điểm): $1\le t\le10$, $1\le n\le10$.

Subtask 2 (30 điểm): $1\le t\le100$, $\sum n\le200$.

Subtask 3 (50 điểm): $1\le t\le2000$, $1\le n\le2000$, $1\le a_i\le2000$, $\sum n\le2000$.

Ví dụ

Input

5
2
2 3
4
2 2 8 8
3
3 3 3
4
5 5 5 5
4
1 1 1 1

Output

YES
NO
YES
NO
NO

Giải thích

Điều kiện quyết định chỉ phụ thuộc số lượng phần tử chẵn/lẻ và parity của tổng.