Chef has an array A of length N. 

Chef forms a binary array B of length N using the parity of the sums of adjacent elements in A. Formally,
B_{i} = (A_{i} + A_{i+1}) \, \% \, 2 for 1 ≤ i ≤ N - 1
B_{N} = (A_{N} + A_{1}) \, \% \, 2

Here x \, \% \, y denotes the remainder obtained when x is divided by y.

Chef lost the array A and needs your help. Given array B, determine whether there exits any valid array A which could have formed B.

------ 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 array A.
- The second line of each test case contains N space-separated integers B_{1}, B_{2}, \dots, B_{N} denoting the array B.

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

For each testcase, output YES if there exists a valid array A, NO otherwise.

You can print any character in any case. For example YES, Yes, yEs are all considered same.

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

$1 ≤ T ≤ 1000$
$2 ≤ N ≤ 10^{5}$
$B_{i} \in \{0, 1\}$
- The sum of $N$ over all test cases do not exceed $3 \cdot 10^{5}$.

----- Sample Input 1 ------ 
4
2
0 0
2
1 0
4
1 0 1 0
3
1 0 0

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

----- explanation 1 ------ 
Test case 1: One such valid array is $A = [3, 3]$.

Test case 2: It can be shown that no such arrays exist and are valid.

Test case 3: One such valid array is $A = [1, 2, 4, 5]$.
- $B_{1} = 1$ since $A_{1} + A_{2} = 1 + 2 = 3$ and $3 \, \% \, 2 = 1$
- $B_{2} = 0$ since $A_{2} + A_{3} = 2 + 4 = 6$ and $6 \, \% \, 2 = 0$
- $B_{3} = 1$ since $A_{3} + A_{4} = 4 + 5 = 9$ and $9 \, \% \, 2 = 1$
- $B_{4} = 0$ since $A_{4} + A_{1} = 5 + 1 = 6$ and $6 \, \% \, 2 = 0$

Difficulty: EASY

Starter code:

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


for _ in range(int(input())):
	N = int(input())
	bin_str = input()
	count_one = bin_str.count('1')
	if count_one % 2 == 0:
		print('YES')
	else:
		print('NO')


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


for j in range(int(input())):
	A = int(input())
	S = input()
	C = S.count('1')
	if C % 2 == 0:
		print('YES')
	else:
		print('NO')


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


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


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


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


t = int(input())
for i in range(t):
	n = int(input())
	a = []
	a = list(map(int, input().split()))
	sum = 0
	for j in range(n):
		sum = sum + a[j]
	if sum % 2 == 0:
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	a = int(input())
	l1 = [int(x) for x in input().split(' ')]
	c = l1.count(1)
	if c % 2 == 0:
		print('YES')
	else:
		print('NO')


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


for i in range(int(input())):
	A = []
	N = int(input())
	B = input()
	c = B.count('1')
	if c % 2 == 0:
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	n = int(input())
	x = input()
	c = x.count('1')
	if c % 2 == 0:
		print('YES')
	if c % 2 != 0:
		print('NO')


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


def valid_array(n, b):
	if sum(b) % 2 == 1:
		return 'NO'
	elif all((b[i] != b[(i + 1) % n] for i in range(n))):
		return 'YES'
	else:
		return 'YES'
t = int(input())
for i in range(t):
	n = int(input())
	b = list(map(int, input().split()))
	print(valid_array(n, b))


for i in range(int(input())):
	n1 = int(input())
	l1 = list(map(int, input().strip().split()))[:n1]
	c = l1.count(1)
	if c % 2 == 0:
		print('YES')
	else:
		print('NO')


t = int(input())
while t:
	n = int(input())
	s = input()
	count = s.count('1')
	if count % 2 == 0:
		print('YES')
	else:
		print('NO')
	t -= 1


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


for _ in range(int(input())):
	n = input()
	s = input()
	c = s.count('1')
	if c % 2 == 0:
		print('YES')
	else:
		print('NO')


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


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


Test = int(input())
for Cases in range(Test):
	SizeofArray = int(input())
	BinaryArray = input()
	Check = BinaryArray.count('1')
	if Check % 2 == 0:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	N = int(input())
	B = tuple(map(int, input().split()))
	ones = B.count(1)
	if ones % 2 == 0:
		print('YES')
	else:
		print('NO')


def solve():
	n = int(input())
	ls = [int(i) for i in input().split(' ', n)]
	a = ls.count(1)
	if a % 2 == 0:
		print('YES')
	else:
		print('NO')
for i in range(int(input())):
	solve()


for _ in range(int(input())):
	u = input()
	y = list(map(int, input().split()))
	if y.count(1) % 2 == 0:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	n = int(input())
	res = 0
	li = list(map(int, input().split()))
	for i in li:
		res ^= i
	if res == 0:
		print('YES')
	else:
		print('NO')


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


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


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


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