Array with Odd Sum (Array with Odd Sum)

Source: Codeforces

Version: Phuoc Hung OJ Extended

Problem

For each test case, an array $a$ of $n$ positive integers is given. In one operation choose distinct indices $i\ne j$ and assign

Any number of operations, including zero, may be performed. Determine whether an array with odd total sum can be obtained.

Input

The first line contains $t$. Each test case contains $n$ and then $n$ integers $a_i$.

Output

For each test case print YES if an odd-sum array can be obtained, otherwise print NO.

Subtask

Subtask 1 (20 points): $1\le t\le10$, $1\le n\le10$.

Subtask 2 (30 points): $1\le t\le100$, $\sum n\le200$.

Subtask 3 (50 points): $1\le t\le2000$, $1\le n\le2000$, $1\le a_i\le2000$, $\sum n\le2000$.

Example

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

Explanation

The sample follows the definitions and rules above.