Problem Description

You are given an array a consisting of n integers.

In one move, you can choose two indices 1≤i,j≤n such that i≠j and set ai:=aj. You can perform such moves any number of times (possibly, zero). You can choose different indices in different operations. The operation := is the operation of assignment (i.e. you choose i and j and replace ai with aj).

Your task is to say if it is possible to obtain an array with an odd (not divisible by 2) sum of elements.

You have to answer t independent test cases.

Input

The first line of the input contains one integer t (1≤t≤2000) — 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 a1,a2,…,an (1≤ai≤2000), where ai is the i-th element of a.

It is guaranteed that the sum of n over all test cases does not exceed 2000 (∑n≤2000).

Output

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

Examples

Input

5
2
2 3
4
2 2 8 8
3
3 3 3
4
5 5 5 5
4
1 1 1 1

Output

YES
NO
YES
NO
NO

題意：t 組數據，每組給出 n 個數，對于任意兩個數 a[i]、a[j]，可以令 a[i]=a[j]，問在有限次操作的情況下，這 n 個數的和是否能變成一個奇數

思路：簡單的思維題，首先，如果這 n 個數全是偶數，那么一定不可能，然后，如果這 n 個數都是奇數，且 n 是一個偶數，那么無論怎么變，偶數個奇數相加一定是偶數，也不可能，排除上述兩種情況外，其他情況全都可能

Source Program

#include<iostream> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<cmath> #include<ctime> #include<algorithm> #include<utility> #include<stack> #include<queue> #include<vector> #include<set> #include<map> #include<bitset> #define PI acos(-1.0) #define INF 0x3f3f3f3f #define LL long long #define Pair pair<int,int> LL quickPow(LL a,LL b){ LL res=1; while(b){if(b&1)res*=a; a*=a; b>>=1;} return res; } LL multMod(LL a,LL b,LL mod){ a%=mod; b%=mod; LL res=0; while(b){if(b&1)res=(res+a)%mod; a=(a<<=1)%mod; b>>=1; } return res%mod;} LL quickMultPowMod(LL a, LL b,LL mod){ LL res=1,k=a; while(b){if((b&1))res=multMod(res,k,mod)%mod; k=multMod(k,k,mod)%mod; b>>=1;} return res%mod;} LL quickPowMod(LL a,LL b,LL mod){ LL res=1; while(b){if(b&1)res=(a*res)%mod; a=(a*a)%mod; b>>=1; } return res; } LL getInv(LL a,LL mod){ return quickPowMod(a,mod-2,mod); } LL GCD(LL x,LL y){ return !y?x:GCD(y,x%y); } LL LCM(LL x,LL y){ return x/GCD(x,y)*y; } const double EPS = 1E-15; const int MOD = 1000000000+7; const int N = 2000+5; const int dx[] = {0,0,1,-1,1,1,-1,-1}; const int dy[] = {1,-1,0,0,1,-1,1,-1}; using namespace std;int a[N]; int main() {int t;scanf("%d", &t);while (t--) {int n;scanf("%d", &n);int odd = 0, even = 0;for (int i = 1; i <= n; i++) {scanf("%d", &a[i]);if (a[i] % 2)odd++;elseeven++;}if (even == n)printf("NO\n");else {if (n % 2 == 0 && odd == n)printf("NO\n");elseprintf("YES\n");}}return 0; }

?

總結

以上是生活随笔為你收集整理的Array with Odd Sum（CF-1296A）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。