Our friend Osman has an array of numbers and is having a problem with them. The array contains \(N\) positive integers. Osman wants to determine if it is possible to make the sum of all the elements in the array equal to an odd (not divisible by 2) number with numerous operations (possibly zero).

In one operation, Osman may choose two indices \(1 \leq i, j \lt N\) and make \(A_i = A_j\). In other words, Osman can choose to assign \(A_j\) to \(A_i\). Your task is to say whether it is possible to obtain an array with an odd sum of elements.

Input:

The first line of the input contains one integer \(T\) \((1 ≤ T ≤ 20)\) — the number of test cases.

The next \(2T\) lines describe test cases. The first line of the test case contains one integer \(N\) \((1 ≤ N ≤ 2000)\) — the number of elements in \(A\). The second line of the test case contains \(N\) integers \(A_1, A_2, … , A_n\) \((1 ≤ A_i ≤ 2000)\), where \(A_i\) is the \(i\)-th element of \(A\).

It is guaranteed that the sum of \(N\) over all test cases does not exceed 2000.

Output

For each test case, print the answer on it — "YES" if it is possible to obtain the array with an odd sum of elements, and "NO" otherwise.

Example

Input:

4
1
7
2
3 5
4
31 31 31 31
5
3 3 3 2 1

Output:

YES
NO
NO
YES