You are given an array $a$ consisting of $n$ integers.

In one move, you can choose two indices $1 \le i, j \le n$ such that $i \ne j$ and set $a_i := a_j$. 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 $a_i$ with $a_j$).

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 \le t \le 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 \le n \le 2000$) — the number of elements in $a$. The second line of the test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 2000$), where $a_i$ is the $i$-th element of $a$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2000$ ($\sum n \le 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.


-----Example-----
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
[{"code": "for _ in range(int(input())):\n    n = int(input())\n    ar = list(map(int, input().split()))\n    a, b = 0, 0\n    for elem in ar:\n        if elem % 2 == 0:\n            a = 1\n        else:\n            b = 1\n    if sum(ar) % 2 == 1:\n        print('YES')\n    elif a == 1 == b:\n        print('YES')\n    else:\n        print('NO')", "passed": true, "time": 0.14, "memory": 14244.0, "status": "done"}, {"code": "for _ in range(int(input())):\n    n = int(input())\n    A = list(map(int, input().split()))\n    c1, c2 = 0, 0\n    for i in A:\n        if i % 2:\n            c1 += 1\n        else:\n            c2 += 1\n    if c1 == 0:\n        print('NO')\n    elif c2 == 0:\n        if n% 2:\n            print('YES')\n        else:\n            print('NO')\n    else:\n        print('YES')\n\n", "passed": true, "time": 0.14, "memory": 14228.0, "status": "done"}, {"code": "import math\nfrom decimal import Decimal\nimport heapq\nimport copy\nimport heapq\nfrom collections import deque\ndef na():\n\tn = int(input())\n\tb = [int(x) for x in input().split()]\n\treturn n,b\n \n\t\ndef nab():\n\tn = int(input())\n\tb = [int(x) for x in input().split()]\n\tc = [int(x) for x in input().split()]\n\treturn n,b,c\n \n\t\t\ndef dv():\n\tn, m = list(map(int, input().split()))\n\treturn n,m\n \n \ndef da():\n\tn, m = list(map(int, input().split()))\n\ta = list(map(int, input().split()))\n\treturn n,m, a \n \n \ndef dva():\n\t\n\tn, m = list(map(int, input().split()))\n\ta = [int(x) for x in input().split()]\n\tb = [int(x) for x in input().split()]\n\treturn n,m,b\n \n \ndef eratosthenes(n): \n\tsieve = list(range(n + 1))\n\tfor i in sieve:\n\t\tif i > 1:\n\t\t\tfor j in range(i + i, len(sieve), i):\n\t\t\t\tsieve[j] = 0\n\treturn sorted(set(sieve))\n \n \ndef lol(lst,k):\n\tk=k%len(lst)\n\tret=[0]*len(lst)\n\tfor i in range(len(lst)):\n\t\tif i+k<len(lst) and i+k>=0:\n\t\t\tret[i]=lst[i+k]\n\t\tif i+k>=len(lst):\n\t\t\tret[i]=lst[i+k-len(lst)]\n\t\tif i+k<0:\n\t\t\tret[i]=lst[i+k+len(lst)]\n\treturn(ret)\ndef nm():\n\tn = int(input())\n\tb = [int(x) for x in input().split()]\n\tm = int(input())\n\tc = [int(x) for x in input().split()]\n\treturn n,b,m,c\n \n \ndef dvs():\n\tn = int(input())\n\tm = int(input())\n\treturn n, m \n \n\ndef fact(n):\n\ttc = []\n\tans = {}\n\td = 2\n\twhile d * d <= n:\n\t\tif n % d == 0:\n\t\t\ttc.append(d)\n\t\t\tn //= d\n\t\telse:\n\t\t\td += 1\n\tif n > 1:\n\t\ttc.append(n)\n\tfor i in tc:\n\t\tans[i] = ans.get(i, 0) + 1\n\treturn ans\n\n\nfor i in range(int(input())):\n\t\tn, a = na()\n\t\tnech = 0\n\t\ts = 0\n\t\tfor j in a:\n\t\t\tif j % 2 == 1:\n\t\t\t\tnech += 1\n\t\t\ts += j\n\t\tif s % 2 == 1:\n\t\t\tprint('YES')\n\t\t\tcontinue\n\t\tif nech == n or nech == 0:\n\t\t\tprint('NO')\n\t\telse:\n\t\t\tprint('YES')\n", "passed": true, "time": 0.15, "memory": 14312.0, "status": "done"}, {"code": "import sys\nimport math\nimport itertools\nimport functools\nimport collections\nimport operator\n\n\ndef ii(): return int(input())\ndef mi(): return map(int, input().split())\ndef li(): return list(map(int, input().split()))\ndef lcm(a, b): return abs(a * b) // math.gcd(a, b)\ndef revn(n): return str(n)[::-1]\ndef dd(): return collections.defaultdict(int)\ndef ddl(): return collections.defaultdict(list)\ndef sieve(n):\n    if n < 2: return list()\n    prime = [True for _ in range(n + 1)]\n    p = 3\n    while p * p <= n:\n        if prime[p]:\n            for i in range(p * 2, n + 1, p):\n                prime[i] = False\n        p += 2\n    r = [2]\n    for p in range(3, n + 1, 2):\n        if prime[p]:\n            r.append(p)\n    return r\ndef divs(n, start=2):\n    r = []\n    for i in range(start, int(math.sqrt(n) + 1)):\n        if (n % i == 0):\n            if (n / i == i):\n                r.append(i)\n            else:\n                r.extend([i, n // i])\n    return r\ndef divn(n, primes):\n    divs_number = 1\n    for i in primes:\n        if n == 1:\n            return divs_number\n        t = 1\n        while n % i == 0:\n            t += 1\n            n //= i\n        divs_number *= t\ndef prime(n):\n    if n == 2: return True\n    if n % 2 == 0 or n <= 1: return False\n    sqr = int(math.sqrt(n)) + 1\n    for d in range(3, sqr, 2):\n        if n % d == 0: return False\n    return True\ndef convn(number, base):\n    newnumber = 0\n    while number > 0:\n        newnumber += number % base\n        number //= base\n    return newnumber\ndef cdiv(n, k): return n // k + (n % k != 0)\n\n\nt = ii()\nfor _ in range(t):\n    n = ii()\n    a = li()\n    if all(a[i] & 1 for i in range(n)) and not n & 1 or all(not a[i] & 1 for i in range(n)):\n        print('NO')\n    else:\n        print('YES')", "passed": true, "time": 0.14, "memory": 14224.0, "status": "done"}, {"code": "def iinput():\n    return [int(x) for x in input().split()]\n\n\ndef main():\n    n = int(input())\n    data = iinput()\n    count = 0\n    for i in range(n):\n        if data[i] % 2 == 1:\n            count += 1\n    if count == 0 or (count == n and n % 2 == 0):\n        return 'NO'\n    else:\n        return 'YES'\n\n\nfor t in range(int(input())):\n    print(main())\n", "passed": true, "time": 0.23, "memory": 14128.0, "status": "done"}, {"code": "t=int(input())\nfor _ in range(t):\n    n=int(input())\n    it=list(map(int,input().split()))\n    s=[i for i in it if i%2==1]\n    if(len(s)>=1 and (len(s)<n or n%2==1)):\n        print(\"YES\")\n    else:\n        print(\"NO\")\n", "passed": true, "time": 0.14, "memory": 14224.0, "status": "done"}, {"code": "t=int(input())\nwhile(t):\n    t-=1\n    n=int(input())\n    a=list(map(int,input().split()))\n    co=0\n    for i in a:\n        if(i%2):\n            co+=1\n    if((co==n and n%2==0) or co==0):\n        print(\"NO\")\n    else:\n        print(\"YES\")\n", "passed": true, "time": 0.21, "memory": 14084.0, "status": "done"}, {"code": "t=int(input())\nfor i in range(t):\n    n=int(input())\n    a=list(map(int,input().split()))\n    odd,even=False,False\n    for i in a:\n        if i%2==0:\n            even=True\n        else:\n            odd=True\n        if odd and even:\n            print('YES')\n            break\n    else:\n        if odd and (not even) and n%2==1:\n            print('YES')\n        else:\n            print('NO')\n", "passed": true, "time": 0.14, "memory": 14300.0, "status": "done"}, {"code": "t = int(input())\nfor zz in range(t):\n    n = int(input())\n    a = [int(i) for i in input().split()]\n    ha = False\n    ho = False\n    he = False\n    for i in a:\n        if i % 2 == 1:\n            ho = True\n        else:\n            he = True\n    if n % 2 == 0:\n        ha = ho and he\n    else:\n        ha = ho\n    if ha:\n        print('YES')\n    else:\n        print('NO')\n", "passed": true, "time": 0.14, "memory": 14100.0, "status": "done"}, {"code": "import math, collections, sys\ninput = sys.stdin.readline\nfor _ in range(int(input())):\n    n = int(input())\n    a = list(map(int, input().split()))\n    oc = 0\n    for i in a:\n        oc+=i%2\n    if oc:\n        if oc%2:\n            print(\"YES\")\n        else:\n            if n-oc:\n                print(\"YES\")\n            else:\n                print(\"NO\")\n    else:\n        print(\"NO\")", "passed": true, "time": 0.14, "memory": 14168.0, "status": "done"}, {"code": "t = int(input())\nfor _ in range(t):\n    n = int(input())\n    a = [int(i) for i in input().split()]\n    o = 0\n    for i in a:\n        if i%2 != 0:\n            o += 1\n    if o == 0:\n        print(\"NO\")\n    elif o == n and n%2 == 0:\n        print(\"NO\")\n    elif o == n and n%2 == 1:\n        print(\"YES\")\n    else:\n        print(\"YES\")\n", "passed": true, "time": 0.14, "memory": 14204.0, "status": "done"}, {"code": "def solve(arr,n):\n    even = 0\n    for i in arr:\n        if i%2 == 0:\n            even += 1\n\n    if even == n:\n        print('NO')\n        return\n    \n    odd = n-even\n\n    if odd == n and n%2 == 0:\n        print('NO')\n        return\n    \n    print('YES')\n\ndef main():\n    t = int(input())\n    for i in range(t):\n        n = int(input())\n        arr = list(map(int,input().split()))\n        solve(arr,n)\n\n    \nmain()\n", "passed": true, "time": 0.14, "memory": 14200.0, "status": "done"}, {"code": "n = int(input())\nfor i in range(n):\n    num = int(input())\n    lst = list(map(int, input().split()))\n    even = 0\n    odd = 0\n    for j in lst:\n        if j % 2 == 0:\n            even+=1\n        else:\n            odd+=1\n    if odd == 0 or (odd == num and num % 2 == 0):\n        print(\"NO\")\n    else:\n        print(\"YES\")", "passed": true, "time": 0.14, "memory": 14244.0, "status": "done"}, {"code": "\n\nfor _ in range(int(input())):\n    n = int(input())\n    a = [int(i) for i in input().split()]\n    \n    if sum(a) % 2 == 1:\n        print('YES')\n    \n    \n    else:\n        par = False\n        impar = False\n        for i in a:\n            if i % 2 == 0:\n                par = True\n            else:\n                impar = True\n        if par and impar:\n            print('YES')\n        else:\n            print('NO')\n            \n\n\n", "passed": true, "time": 0.14, "memory": 14192.0, "status": "done"}, {"code": "for _ in range(int(input())):\n\tn = int(input())\n\tarr = list(map(int, input().split()))\n\tif sum(arr)%2 == 1:\n\t\tprint('YES')\n\telif all(ele%2 == 0 for ele in arr):\n\t\tprint('NO')\n\telif all(ele%2 == 1 for ele in arr) and len(arr)%2 == 0:\n\t\tprint('NO')\n\telse:\n\t\tprint('YES')", "passed": true, "time": 0.14, "memory": 14172.0, "status": "done"}]