Chef had an array A of length N such that 1 ≤ A_{i} ≤ N for all 1 ≤ i ≤ N. Chef constructed another binary array B of length N in the following manner:
B_{i} = 1 if the frequency of element i in A is *odd*.
B_{i} = 0 if the frequency of element i in A is *even*.

Such an array B is called the *parity encoding* array of A.

For example, if A = [1, 1, 2, 3], then B = [0, 1, 1, 0].

Unfortunately, Chef completely forgot the array A and vaguely remembers the *parity encoding* array B. He is now wondering whether there exists any valid array A for which the *parity encoding* array is B. Can you help Chef?

------ Input Format ------ 

- The first line contains a single integer T — the number of test cases. Then the test cases follow.
- The first line of each test case contains an integer N — the size of the arrays A and B.
- The second line of each test case contains N space-separated integers B_{1}, B_{2}, \dots, B_{N} denoting the *parity encoding* array B.

------ Output Format ------ 

For each test case, output YES if there exists any valid array A for which the *parity encoding* array is B. Otherwise, output NO.

You may print each character of YES and NO in uppercase or lowercase (for example, yes, yEs, Yes will be considered identical).

------ Constraints ------ 

$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 10^{5}$
$B_{i} \in \{0, 1\}$
- Sum of $N$ over all test cases does not exceed $2 \cdot 10^{5}$.

----- Sample Input 1 ------ 
3
4
0 1 0 1
5
1 1 1 1 0
6
1 1 1 1 1 1

----- Sample Output 1 ------ 
YES
NO
YES

----- explanation 1 ------ 
Test case $1$: $A = [2, 4, 3, 3]$ is a valid array for the given array $B$.

Test case $2$: It can be proven that there does not exist any array $A$ for the given parity encoding array $B$.

Test case $3$: $A = [1, 2, 3, 4, 5, 6]$ is a valid array for the given array $B$.

Difficulty: EASY

Starter code:

Solutions:
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if n % 2 == sum(a) % 2:
		print('YES')
	else:
		print('NO')


s = int(input())
for i in range(s):
	a = int(input())
	b = list(map(int, input().split(' ')))
	c = b.count(0)
	if c % 2 == 0:
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	k = int(input())
	l = list(map(int, input().split()))
	if k % 2 == sum(l) % 2:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	n = int(input())
	s = list(map(int, input().split()))
	c = 0
	for num in s:
		if num == 1:
			c = c + 1
	if n % 2 == 0:
		if c % 2 == 0:
			print('YES')
		else:
			print('NO')
	elif c % 2 == 0:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	n = int(input())
	l = [int(i) for i in input().split()]
	if n - sum(l) & 1:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	n = int(input())
	b = list(map(int, input().split()[:n]))
	x = b.count(1)
	y = b.count(0)
	n = n - x
	if n % 2 == 0 and n != 0:
		if y > 0:
			print('YES')
		else:
			print('NO')
	elif n == 0:
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	n = int(input())
	b = list(map(int, input().split()))
	if b.count(0) % 2 == 0:
		print('YES')
	else:
		print('NO')


def bs(arr, n, k, low, high):
	c = 0
	while low <= high:
		mid = (low + high) // 2
		if arr[mid] == k:
			c += 1
		elif arr[mid] < k:
			low = mid + 1
		else:
			high = mid - 1
	return c
for i in range(int(input())):
	n = int(input())
	arr = [int(x) for x in input().split()]
	z = arr.count(0)
	o = arr.count(1)
	if (n - o) % 2 == 0:
		print('YES')
	else:
		print('NO')


T = int(input())
for i in range(T):
	N = int(input())
	L = input()
	c = L.count('0')
	if c % 2 == 0:
		print('YES')
	else:
		print('NO')


for testcases in range(int(input())):
	n = int(input())
	l = list(map(int, input().strip().split()))[:n]
	if n % 2 == sum(l) % 2:
		print('YES')
	else:
		print('NO')


n = int(input())
for i in range(n):
	num = int(input())
	A = list(map(int, input().split()))
	if num % 2 == sum(A) % 2:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	N = int(input())
	B = [int(j) for j in input().split()][:N]
	c = 0
	d = 0
	for k in B:
		if k == 1:
			c += 1
		if k == 0:
			d += 1
	if N % 2 == 0:
		if c % 2 == 0:
			print('YES')
		else:
			print('NO')
	elif c % 2 == 1:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	n = int(input())
	arr_B = input()
	if arr_B.count('0') % 2 == 0:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	c = 0
	for v in l:
		if v == 0:
			c = c + 1
	if c % 2 == 0:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	o = 0
	e = 0
	for ow in l:
		if ow == 0:
			o += 1
	if o % 2 == 0:
		print('YES')
	else:
		print('NO')


T = int(input())
for i in range(T):
	n = int(input())
	B = list(map(int, input().split()))
	if n % 2 == sum(B) % 2:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	n = int(input())
	lst = list(map(int, input().split()))
	if n % 2 == sum(lst) % 2:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	n = int(input())
	s = list(map(int, input().split()))
	if n % 2 == 0 and s.count(1) % 2 == 0:
		print('YES')
	elif n % 2 == 1 and s.count(1) % 2 == 1:
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	n = int(input())
	a = input()
	if a.count('0') % 2 == 0:
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	c = a.count(1)
	if n % 2 == 0 and c % 2 != 0:
		print('NO')
	elif n % 2 == 1 and c % 2 == 0:
		print('NO')
	else:
		print('YES')


t = int(input())
while t > 0:
	n = int(input())
	list1 = list(map(int, input().split()))
	z = list1.count(0)
	if z % 2 == 0:
		print('YES')
	else:
		print('NO')
	t = t - 1


for _ in range(int(input())):
	n = int(input())
	b = list(map(int, input().split()))
	print('YES' if n % 2 == 0 and sum(b) % 2 == 0 or (n % 2 and sum(b) % 2) else 'NO')


for i in range(int(input())):
	roxy = int(input())
	nancy = map(int, input().split())
	if roxy % 2 == sum(nancy) % 2:
		print('YES')
	else:
		print('NO')


input_ = int(input())
for i in range(input_):
	inp = input()
	binary = [*map(str, input().split())]
	countzero = 0
	for i in binary:
		if i == '0':
			countzero += 1
	check = countzero % 2
	if check == 0:
		print('YES')
	else:
		print('NO')


for j in range(int(input())):
	n = int(input())
	b = list(map(int, input().split()))
	l = b.count(1) % 2
	k = n % 2
	if l == k:
		print('YES')
	else:
		print('NO')


for t in range(int(input())):
	n = int(input())
	brr = list(map(int, input().split()))
	print('YES' if brr.count(0) % 2 == 0 else 'NO')


for _ in range(int(input())):
	n = int(input())
	b = list(map(int, input().split()))
	count1 = 0
	for i in range(n):
		if b[i] == 1:
			count1 += 1
	if n % 2 == 0:
		if count1 % 2 == 0:
			print('YES')
		else:
			print('NO')
	elif count1 % 2 == 0:
		print('NO')
	else:
		print('YES')


T = int(input())
for _ in range(T):
	n = int(input())
	b = list(map(int, input().split()))
	a = b.count(0)
	if a % 2 == 0:
		print('YES')
	else:
		print('NO')


cases = int(input())
for i in range(cases):
	N = int(input())
	B = map(int, list(input().split()))
	if N % 2 == sum(B) % 2:
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	num = int(input())
	lis = list(map(int, input().split(' ')))
	even = lis.count(0)
	if even % 2 == 0:
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	k = a.count(1)
	if n % 2 == k % 2:
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	m = l.count(1)
	if n % 2 == 1 and m % 2 == 1:
		print('YES')
	elif n % 2 == 0 and m % 2 == 0:
		print('YES')
	else:
		print('NO')