Question
Counting Problem

You are given an array A = [A1​, A2​,…, AN]. Is it possible to partition A into two non-empty subsequences S1​ and S2​ such that sum(S1​) x sum(S2) is odd?
Here, sum(S1​) denotes the sum of elements in S1​, and sum(S2​) is defined similarly.
Note: S1​ and S2​ must partition A, that is:

  • S1​ and S2​ must be non-empty.
  • Every element of A must be in either S1​ or S2​.
  • S1​ and S2​ must be disjoint (in terms of which indices their subsequences represent)
Input
The first line of input will contain a single integer T, denoting the number of test cases.
Each test case consists of 2 lines of input.
The first line of each test case contains a single integer N, the size of the array.
The next line contains N space-separated integers A1, A2..., AN, denoting the elements of the array.

Constraints
1 ≤ T ≤ 105
2 ≤ N ≤ 105
1 ≤ Ai ≤ 109
Note: The sum of N across all test cases won't exceed 106
Output
For each test case, print on a new line the answer: Yes if the array can be partitioned into two subsequences satisfying the condition, and No otherwise.

Example
Input
2
4
1 1 2 2
6
1 2 4 6 8 10
Output
Yes
No
Explanation
Test case 1: We have A = [1, 1, 2, 2]. Let S1 be the underlined elements and S2 be the other ones. sum (S1) x sum (S2 = 3 x 3 = 9
Test case 2: It can be proved that no partition of A into S1, S2 satisfies the condition.

Online