Integer Average Rearrangement

You are given T test cases. For each test case, you are given an integer N and an array of N integers. Your task is to determine whether there exists a rearrangement of the array such that there is at least one contiguous subarray whose arithmetic mean is an integer.

It can be proven that such a rearrangement exists if and only if the given array contains both an even number and an odd number. In other words, if there exist indices i and j such that \[ a_i \bmod 2 \neq a_j \bmod 2, \] then the answer is YES; otherwise, the answer is NO.

Note: The arithmetic mean of a subarray is computed as the sum of its elements divided by the number of elements. A rearrangement is any permutation of the array.

inputFormat

The input is given from standard input and has the following format:

T
N₁
a₁ a₂ ... aₙ₁
N₂
a₁ a₂ ... aₙ₂
...
Nₜ
a₁ a₂ ... aₙₜ

Here, T is the number of test cases. For each test case, the first line contains an integer N, and the second line contains N space-separated integers representing the array.

outputFormat

For each test case, output a single line containing YES if a valid rearrangement exists, or NO otherwise. The answers for the test cases should be output in the same order as the input.

1
3
1 2 3

YES