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
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.
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.