Taco Rearrangement Challenge

Given a sequence of integers, determine whether it is possible to rearrange the sequence so that no two adjacent elements have the same parity. Two elements have the same parity if both are even or both are odd. A necessary and sufficient condition is that the absolute difference between the number of even and odd elements satisfies (|\text{even} - \text{odd}| \leq 1). If this condition holds, a valid rearrangement exists.

inputFormat

The first line contains an integer (T) denoting the number of test cases. Each test case consists of two lines. The first line has an integer (N) representing the number of elements in the sequence, and the second line contains (N) space-separated integers.

outputFormat

For each test case, output a single line containing "YES" if the sequence can be rearranged such that no adjacent elements have the same parity; otherwise, output "NO".## sample

3
3
1 2 3
4
2 4 6 8
5
1 3 5 7 9

YES
NO
NO