You are given an array A and an integer X. You are allowed to perform the following operation on the array:
Select two distinct indices i and j and set both A_{i} and A_{j} as ((A_{i} \oplus A_{j}) \mid X) simultaneously. Here \oplus and \mid denote the [bitwise XOR] and [bitwise OR] operations respectively.

Find the minimum number of operations required to make all elements of the array odd. If it is not possible to do so, print -1 instead.

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

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of two lines of input.
- The first line of each test case contains two space-separated integers N, the size of the array and X.
- The next line contains N space-separated integers denoting the elements of the array A.

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

For each test case, output on a new line, the minimum number of operations required to make all elements of the array odd. If it is not possible to do so, print -1 instead.

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

$1 ≤ T ≤ 10^{5}$
$2 ≤ N ≤ 10^{5}$
$0 ≤ X < 2^{30}$
$0 ≤ A_{i} < 2^{30}$
- The sum of $N$ over all test cases won't exceed $10^{5}$.

----- Sample Input 1 ------ 
2
3 6
5 7 9
5 4
2 3 4 17 9

----- Sample Output 1 ------ 
0
2
----- explanation 1 ------ 
Test case $1$: All elements are already odd. Thus, the number of operation required will be $0$.

Test case $2$: We can make all elements odd using $2$ operations -
- In first operation, we choose $i=1, j=5$.  
Here, $(A_{i}\oplus A_{j})\mid X=(2 \oplus 9)\mid 4 = 11 \mid 4 = 15$. Thus, the new array becomes $[15,3,4,17,15]$.
- In second operation, we choose $i=4, j=3$.  
Here, $(A_{i}\oplus A_{j})\mid X=(17 \oplus 4)\mid 4 = 21 \mid 4 = 21$. Thus, the new array becomes $[15,3,21, 21,15]$.

All elements of the array are odd now. It can be shown that we cannot achieve this in less than $2$ operations.

Source: codechef | Difficulty: MEDIUM
Tags: Bit manipulation

Mathematics


Solutions:
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	l = map(int, input().split())
	c = 0
	for i in l:
		if i % 2 == 0:
			c = c + 1
	if k & 1:
		if c & 1:
			print(c // 2 + 1)
		else:
			print(c // 2)
	elif c != n:
		print(c)
	else:
		print(-1)


from math import ceil
for _ in range(int(input())):
	(n, x) = map(int, input().strip().split())
	a = [int(x) % 2 for x in input().strip().split()]
	x %= 2
	b = sum(a)
	if not b and (not x):
		print(-1)
	else:
		need_change = n - b
		if x:
			print(ceil(need_change / 2))
		else:
			print(need_change)


for tc in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	(e, o) = (0, 0)
	for ele in arr:
		if ele % 2 == 0:
			e += 1
		else:
			o += 1
	if k % 2 == 1:
		if e % 2 == 0:
			req = e // 2
		else:
			req = e // 2 + 1
	elif o:
		req = e
	else:
		req = -1
	print(req)


t = int(input())
for _ in range(t):
	(n, x) = map(int, input().split())
	l = list(map(int, input().split()))
	o = len(list(filter(lambda x: x % 2 != 0, l)))
	if o == len(l):
		print(0)
	elif x % 2 == 0:
		if o > 0:
			print(n - o)
		else:
			print(-1)
	elif (n - o) % 2 == 0:
		print((n - o) // 2)
	else:
		print((n - o) // 2 + 1)


def makeOddg():
	(g1, g2, gc) = (0, 0, 0)
	(g1, g2) = map(int, input().split())
	gupta = [int(g2) for g2 in input().split()]
	for m in range(g1):
		if gupta[m] % 2 == 0:
			gc = gc + 1
	if g2 % 2:
		if gc % 2:
			print(gc // 2 + 1)
		else:
			print(gc // 2)
	elif gc != g1:
		print(gc)
	else:
		print(-1)
test = int(input())
for m in range(test):
	makeOddg()


import math
for i in range(int(input())):
	(n, x) = map(int, input().split())
	li = list(map(int, input().split()))
	o = 0
	e = 0
	for i in range(n):
		if li[i] % 2 == 0:
			e += 1
	o = n - e
	if o == 0 and x % 2 == 0:
		print(-1)
	elif x % 2 != 0:
		print(math.ceil(e / 2))
	else:
		print(e)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	(even, odd) = (0, 0)
	for i in arr:
		if i & 1:
			odd += 1
	even = n - odd
	if k % 2 == 0 and odd == 0:
		print(-1)
	elif k & 1:
		if even % 2 == 0:
			print(even // 2)
		else:
			print(even // 2 + 1)
	else:
		print(even)


t = int(input())
for i in range(t):
	(n, x) = map(int, input().split())
	arr = list(map(int, input().split()))
	count_even = 0
	count_odd = 0
	for i in arr:
		if i % 2 == 0:
			count_even += 1
		else:
			count_odd += 1
	if count_even == n:
		if x % 2:
			if n % 2:
				print(n // 2 + 1)
			else:
				print(n // 2)
		else:
			print(-1)
	elif count_odd == n:
		print(0)
	elif x % 2:
		if count_even % 2:
			print(count_even // 2 + 1)
		else:
			print(count_even // 2)
	else:
		print(count_even)


z = int(input())
for _ in range(z):
	(n, x) = map(int, input().split(' '))
	count = 0
	l = list(map(int, input().split(' ')))
	even = 0
	for a in l:
		if a % 2 == 0:
			even += 1
	if even == n and x % 2 == 0:
		print('-1')
	elif even == 0:
		print('0')
	elif x % 2 == 0:
		print(even)
	else:
		print((even + 1) // 2)


t = int(input())
for i in range(t):
	arr_det = input().split(' ')
	arr = input().split(' ')
	(l_odd, l_even) = ([], [])
	for j in range(int(arr_det[0])):
		if int(arr[j]) % 2 == 0:
			l_even.append(int(arr[j]))
		else:
			l_odd.append(int(arr[j]))
	if len(l_odd) == len(arr):
		print(0)
	elif int(arr_det[1]) % 2 != 0:
		print(len(l_even) // 2 + len(l_even) % 2)
	elif int(arr_det[1]) % 2 == 0 and len(l_odd) != 0:
		print(len(l_even))
	else:
		print(-1)


t = int(input())
for i in range(t):
	(n, x) = map(int, input().split())
	even = 0
	l = [int(a) for a in input().split()]
	for a in l:
		if a % 2 == 0:
			even += 1
	if even == n and x % 2 == 0:
		print('-1')
	elif even == 0:
		print('0')
	elif x % 2 == 0:
		print(even)
	else:
		print((even + 1) // 2)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
testCases_vegesh = int(input())
for vegesh in range(testCases_vegesh):
	(n, p) = map(int, input().split())
	list_vegesh = list(map(int, input().split()))
	even_vegesh = 0
	brnvlw = 0
	snvlbf = 0
	fhbfjweb = 0
	vfbjbfwknfq = 0
	fhcvhbfhwebfeqkj = 1
	for i in list_vegesh:
		if i % 2 == 0:
			even_vegesh += 1
	if p % 2:
		if even_vegesh % 2:
			print(even_vegesh // 2 + 1)
		else:
			print(even_vegesh // 2)
	elif even_vegesh == n:
		print(-1)
	else:
		print(even_vegesh)


for i in range(int(input())):
	(x, y) = map(int, input().split())
	l = list(map(int, input().split()))
	e = 0
	for i in range(x):
		if l[i] % 2 == 0:
			e = e + 1
	if y % 2:
		c = e // 2
		if e % 2 == 0:
			print(c)
		else:
			print(c + 1)
	elif e == x:
		print('-1')
	else:
		print(e)


t = int(input())
while t:
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	c = sum((p & 1 for p in a))
	if x % 2 == 0:
		if c >= 1:
			print(n - c, end='\n')
		else:
			print(-1, end='\n')
	else:
		print((n - c) // 2 + (n - c) % 2, end='\n')
	t -= 1


def solve(even, odd, x):
	if even == 0:
		return 0
	if x % 2 == 1:
		return (even + 1) // 2
	if odd == 0:
		return -1
	return even
import math
t = int(input())
for i in range(t):
	(n, x) = map(int, input().split())
	arr = list(map(int, input().split()))
	(odd, even) = (0, 0)
	for i in arr:
		if i % 2 == 0:
			even += 1
		else:
			odd += 1
	print(solve(even, odd, x))


t = int(input())
for _ in range(t):
	(n, x) = map(int, input().split())
	arr = list(map(int, input().lstrip().split()))
	even = []
	odd = []
	count = 0
	j = 0
	k = len(odd) - 1
	for i in range(n):
		if arr[i] % 2 == 0:
			even.append(arr[i])
		else:
			odd.append(arr[i])
	if len(even) == 0:
		print(0)
	elif len(odd) == 0 and x % 2 == 0 and (len(even) > 0):
		print(-1)
	elif x % 2 == 0:
		print(len(even))
	else:
		print((len(even) + 1) // 2)


import math
for _ in range(int(input())):
	a = list(map(int, input().split()))
	b = input().split()
	ev = 0
	od = 0
	for x in b:
		if int(x) % 2 == 0:
			ev += 1
		else:
			od += 1
	if a[1] % 2 == 1:
		print(ev // 2 + ev % 2)
	elif od >= ev:
		print(ev)
	elif od == 0:
		print(-1)
	elif od < ev:
		print(ev)


for _ in range(int(input())):
	(n, x) = map(int, input().split())
	arr = list(map(int, input().split()))
	even = 0
	for i in arr:
		if i % 2 == 0:
			even += 1
	if x & 1:
		if even & 1:
			print(even // 2 + 1)
		else:
			print(even // 2)
	elif even != n:
		print(even)
	else:
		print(-1)


import math
T = int(input())
for tc in range(T):
	(n, x) = map(int, input().split(' '))
	l = list(map(int, input().split(' ')))
	odd = 0
	even = 0
	for j in l:
		if j % 2 != 0:
			odd += 1
		else:
			even += 1
	if x % 2:
		print(math.ceil(even / 2))
	elif odd != 0:
		print(even)
	else:
		print(-1)


t = int(input())
while t > 0:
	(n, x) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	codd = 0
	for i in range(n):
		if a[i] % 2 == 1:
			codd += 1
	if x % 2 == 1:
		ans = (n - codd) // 2 + (n - codd) % 2
	elif codd == 0:
		ans = -1
	else:
		ans = n - codd
	print(ans)
	t -= 1


import math
tc = int(input())
for _ in range(tc):
	inp = list(map(int, input().split()))
	n = inp[0]
	x = inp[1]
	arr = list(map(int, input().split()))
	eve = 0
	for i in arr:
		if i % 2 == 0:
			eve += 1
	if x % 2 == 0:
		if eve == n:
			print(-1)
		else:
			print(eve)
	else:
		print(math.ceil(eve / 2))


import math
t = int(input())
while t > 0:
	t = t - 1
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	num = 0
	for i in a:
		if i % 2 == 0:
			num += 1
	if x % 2 == 1:
		print(math.ceil(num / 2.0))
	if x % 2 == 0:
		if num == n:
			print(-1)
		else:
			print(num)


import math
t = int(input())
while t > 0:
	(l, x) = input().split()
	l = int(l)
	x = int(x)
	a = [int(i) for i in input().split()]
	even = 0
	for i in range(l):
		if a[i] % 2 == 0:
			even += 1
	if x % 2 != 0:
		if even % 2 == 0:
			print(even // 2)
		else:
			print(even // 2 + 1)
	elif even == l:
		print(-1)
	else:
		print(even)
	t -= 1


import sys

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def get_list():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_list_string():
	return list(map(str, sys.stdin.readline().strip().split()))

def get_string():
	return sys.stdin.readline().strip()

def get_int():
	return int(sys.stdin.readline().strip())

def get_print_int(x):
	sys.stdout.write(str(x) + '\n')

def get_print(x):
	sys.stdout.write(x + '\n')

def get_print_int_same(x):
	sys.stdout.write(str(x) + ' ')

def get_print_same(x):
	sys.stdout.write(x + ' ')
from sys import maxsize
from math import ceil

def solve():
	for _ in range(get_int()):
		(n, x) = get_ints()
		arr = get_list()
		evens = 0
		for i in range(n):
			if arr[i] % 2 == 0:
				evens += 1
		if x % 2 == 1:
			get_print_int(ceil(evens / 2))
		else:
			odds = n - evens
			if odds > 0:
				get_print_int(evens)
			else:
				get_print_int(-1)
solve()


import math
x = int(input())
while x:
	(a, b) = map(int, input().split())
	l = list(map(int, input().split()))
	c = 0
	for i in l:
		if i % 2 == 0:
			c = c + 1
	if c == a and b % 2 == 0:
		print('-1')
	elif c == 0:
		print('0')
	elif b % 2 == 1:
		if c % 2 == 0:
			print(int(c / 2))
		else:
			print(int(c / 2 + 1))
	else:
		print(c)
	x = x - 1


for w in range(int(input())):
	s1 = input().split()
	(s, x) = (int(s1[0]), int(s1[1]))
	arr = input().split()
	evenc = 0
	ans = 0
	for i in arr:
		if int(i) % 2 == 0:
			evenc += 1
	oc = s - evenc
	if x % 2 == 0:
		if oc > 0:
			ans = evenc
		else:
			ans = -1
	else:
		ans = evenc // 2
		if evenc % 2 == 1:
			ans += 1
	print(ans)


for _ in range(int(input())):
	(n, x) = list(map(int, input().split()))
	l = list(map(int, input().split()))
	d = {}
	d[0] = 0
	d[1] = 0
	for i in l:
		d[i % 2] += 1
	if d[0] == 0:
		print(0)
	elif x % 2 == 1:
		if d[0] % 2 == 1:
			d[0] += 1
		c = d[0] // 2
		print(c)
	elif d[1] != 0:
		print(d[0])
	else:
		print(-1)


import math as m
t = int(input())
for i in range(t):
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	c = 0
	d = 0
	for i in a:
		if i % 2 == 0:
			c = c + 1
		else:
			d = d + 1
	if x & 1 == 1:
		print(m.ceil(c / 2))
	elif d == 0:
		print(-1)
	else:
		print(c)


for t in range(int(input())):
	(n, x) = map(int, input().split())
	l = list(map(int, input().split()))
	e = 0
	for i in l:
		if i % 2 == 0:
			e += 1
	if x % 2 == 0 and len(l) - e == 0:
		print(-1)
	elif x % 2 == 1:
		print((e + 1) // 2)
	else:
		print(e)


import math
for _ in range(int(input())):
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	count = 0
	for i in a:
		if i % 2 == 0:
			count += 1
	if count == n and x % 2 == 0:
		print(-1)
	elif x % 2:
		print(math.ceil(count / 2))
	else:
		print(count)


testcases = int(input())
for eachcase in range(testcases):
	(length, x) = map(int, input().split())
	array = list(map(int, input().split()))
	oddcount = 0
	for nums in array:
		if nums & 1:
			oddcount += 1
	evencount = length - oddcount
	if evencount == length and x % 2 == 0:
		print(-1)
	elif x % 2 == 0:
		print(evencount)
	else:
		print(evencount // 2 + evencount % 2)


t = int(input())
for i in range(t):
	(n, x) = map(int, input().split())
	listin = map(int, input().split())
	(odd, even) = (0, 0)
	for p in listin:
		if p % 2 == 0:
			even += 1
		else:
			odd += 1
	if x % 2 == 1:
		if even % 2 == 1:
			print(even // 2 + 1)
		else:
			print(even // 2)
	elif even != n:
		print(even)
	else:
		print(-1)


for i in range(int(input())):
	(n, x) = map(int, input().split())
	l = list(map(int, input().split()))
	l1 = list(filter(lambda x: x % 2 == 0, l))
	r1 = len(l1)
	r2 = len(l) - r1
	if n == 1:
		if l[0] % 2 == 0:
			print('-1')
		else:
			print('1')
		exit()
	if x % 2 == 0:
		if r2 == 0:
			print('-1')
		else:
			print(r1)
	else:
		res1 = int(r1 / 2)
		rem = r1 % 2
		if rem != 0:
			print(res1 + 1)
		else:
			print(res1)


import math

def Solve(a, n, x):
	(even, odd) = (0, 0)
	for i in a:
		if i & 1 == 1:
			odd += 1
		else:
			even += 1
	if x & 1 == 1:
		return math.ceil(even / 2)
	if odd == 0:
		return -1
	return even
for _ in range(int(input())):
	(n, x) = map(int, input().split())
	l = list(map(int, input().split()))
	print(Solve(l, n, x))


import bisect
import fractions
import heapq
import functools
import itertools
import math

def LII():
	return [int(x) for x in input().split()]

def LII1():
	return [int(x) - 1 for x in input().split()]

def II():
	return int(input())
for _ in range(int(input())):
	(n, x) = LII()
	a = [i % 2 for i in LII()]
	assert len(a) == n
	c = a.count(0)
	if x % 2 == 1:
		print((c + 1) // 2)
	elif c != n:
		print(c)
	else:
		print(-1)


t = int(input())
for _ in range(t):
	(n, x) = map(int, input().split())
	l = list(map(int, input().split()))
	odds = 0
	for i in l:
		if i % 2:
			odds += 1
	evens = n - odds
	ans = -1
	if x % 2:
		ans = evens // 2
		if evens % 2:
			ans += 1
	elif odds != 0:
		ans = evens
	print(ans)


import math
for _ in range(int(input())):
	(n, x) = map(int, input().split())
	l = list(map(int, input().split()))
	(o, e) = (0, 0)
	for element in l:
		if element % 2:
			o += 1
		else:
			e += 1
	if x % 2:
		print(math.ceil(e / 2))
	elif o == 0:
		print(-1)
	else:
		print(e)


for _ in range(int(input())):
	(N, X) = map(int, input().split())
	A = list(map(int, input().split()))
	cnt_odd = sum([1 for i in A if i % 2 == 1])
	if cnt_odd == N:
		print(0)
	elif X % 2 == 0 and cnt_odd == 0:
		print(-1)
	elif X % 2 == 0 and cnt_odd != 0:
		print(N - cnt_odd)
	else:
		print((N - cnt_odd) // 2 + (N - cnt_odd) % 2)


def main():
	(n, X) = map(int, input().split())
	l = list(map(int, input().split()))
	even = []
	odd = []
	for i in l:
		if i % 2 == 1:
			odd.append(i)
		else:
			even.append(i)
	if len(even) == 0:
		print(0)
	elif X % 2 == 0:
		if len(odd) == 0:
			print(-1)
		else:
			print(len(even))
	else:
		print(len(even) // 2 + len(even) % 2)
for testcase in range(int(input())):
	main()


t = int(input())
while t > 0:
	(n, x) = map(int, input().split())
	a = [int(i) for i in input().split()]
	(o, e) = (0, 0)
	for i in a:
		if i & 1:
			o += 1
		else:
			e += 1
	if x & 1:
		print(e % 2 + e // 2)
	elif o == 0:
		print(-1)
	else:
		print(e)
	t -= 1


for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	c = 0
	for i in range(n):
		if arr[i] % 2 == 0:
			c += 1
	if c == 0:
		print(0)
		continue
	if k % 2 == 1:
		print((c + 1) // 2)
	elif c == n:
		print(-1)
	else:
		print(c)


t = int(input())
for _ in range(t):
	(n, x) = map(int, input().split(' '))
	arr = list(map(int, input().split(' ')))
	(even, odd) = (0, 0)
	for ele in arr:
		if ele % 2 == 0:
			even += 1
		else:
			odd += 1
	if x % 2 == 1:
		if even % 2:
			print(even // 2 + 1)
		else:
			print(even // 2)
	elif even == n:
		print(-1)
	else:
		print(even)


from math import ceil
for _ in range(int(input())):
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	even = 0
	odd = 0
	for i in a:
		if i % 2 == 0:
			even += 1
		else:
			odd += 1
	if len(a) == odd:
		print(0)
	elif len(a) == even:
		if x % 2 == 0:
			print(-1)
		elif even % 2 == 0:
			print(even // 2)
		else:
			print(even // 2 + 1)
	elif x % 2 == 0:
		print(even)
	elif even % 2 == 0:
		print(even // 2)
	else:
		print(even // 2 + 1)


for i in range(int(input())):
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	o = 0
	e = 0
	for i in range(n):
		if a[i] % 2 == 0:
			e += 1
		else:
			o += 1
	if e == 0:
		print(0)
	elif o == 0 and x % 2 == 0:
		print(-1)
	elif x % 2 == 0:
		print(e)
	elif x % 2 == 1:
		if e % 2 == 0:
			print(e // 2)
		else:
			print(e // 2 + 1)


for _ in range(int(input())):
	(n, x) = [int(x) for x in input().split()]
	(odds, evens) = (0, 0)
	for i in input().split():
		if int(i) % 2 == 1:
			odds += 1
		else:
			evens += 1
	if evens == 0:
		print(0)
	elif x % 2 == 1:
		print(evens // 2 + evens % 2)
	elif n - evens == 0:
		print(-1)
	else:
		print(evens)


import math
T = int(input())
for _ in range(T):
	(N, X) = map(int, input().split())
	A = list(map(int, input().split()))
	(odd, even) = (0, 0)
	for i in A:
		if i % 2 == 1:
			odd += 1
		else:
			even += 1
	if odd == 0 and X % 2 == 0:
		print(-1)
	elif X % 2 == 1:
		print(math.ceil(even / 2))
	else:
		print(even)


for _ in range(int(input())):
	(n, x) = map(int, input().split())
	mao = [int(i) for i in input().split()]
	(even, odd) = (0, 0)
	for num in mao:
		if num % 2:
			odd += 1
	even = n - odd
	if x % 2 == 0 and even == n:
		print(-1)
	elif even == 0:
		print(0)
	elif x & 1:
		if even & 1:
			print(even // 2 + 1)
		else:
			print(even // 2)
	else:
		print(even)


for i in range(int(input())):
	(a, b) = map(int, input().split())
	l = list(map(int, input().split()))
	counteven = 0
	countodd = 0
	for j in range(a):
		if l[j] % 2 == 0:
			counteven += 1
		else:
			countodd += 1
	if counteven == 0:
		print(0)
	elif b % 2 == 0:
		if countodd == 0:
			print(-1)
		else:
			print(counteven)
	else:
		print((counteven + 1) // 2)


import math
for t in range(int(input())):
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	o = sum(map(lambda x: x & 1, a))
	if o == 0 and x & 1 == 0:
		print(-1)
		continue
	if x & 1 == 1:
		print(math.ceil((n - o) / 2))
	else:
		print(n - o)


import math
t = int(input())
while t:
	(n, x) = [int(i) for i in input().split()]
	l = [int(i) for i in input().split()]
	(ce, co) = (0, 0)
	for i in l:
		if i % 2 == 0:
			ce += 1
		else:
			co += 1
	if x % 2 == 1:
		print(math.ceil(ce / 2))
	elif co == 0:
		print(-1)
	else:
		print(ce)
	t -= 1


def count(l):
	j = 0
	for i in l:
		if i % 2 == 0:
			j += 1
	k = len(l) - j
	return [j, k]
import math
a = int(input())
for i in range(a):
	l1 = list(map(int, input().split()))
	l2 = list(map(int, input().split()))
	t = 0
	v = count(l2)
	v_even = v[0]
	v_odd = v[1]
	if l1[1] % 2 == 1:
		print(math.ceil(v_even / 2))
	elif v_odd == 0 and l1[1] % 2 == 0:
		print(-1)
	else:
		print(v_even)


t = int(input())
for tt in range(t):
	(n, x) = map(int, input().split())
	l = list(map(int, input().split()))
	even = 0
	for i in l:
		if i % 2 == 0:
			even += 1
	odd = n - even
	if odd == n:
		print('0')
	elif x % 2 == 0:
		if even == n:
			print('-1')
		else:
			print(even)
	elif even % 2 == 0:
		print(int(even / 2))
	else:
		print(int(even / 2) + 1)


import random
import math
from collections import defaultdict, Counter, deque, OrderedDict
from heapq import heapify, heappush, heappop
from functools import lru_cache, reduce
from bisect import bisect_left, bisect_right
import sys
input = lambda : sys.stdin.readline().strip()

class SegmentTree:

	def __init__(self, arr, func=lambda x, y: x + y, defaultvalue=0):
		self.n = len(arr)
		self.segmentTree = [0] * self.n + arr
		self.func = func
		self.defaultvalue = defaultvalue
		self.buildSegmentTree(arr)

	def buildSegmentTree(self, arr):
		for i in range(self.n - 1, 0, -1):
			self.segmentTree[i] = self.func(self.segmentTree[2 * i], self.segmentTree[2 * i + 1])

	def query(self, l, r):
		l += self.n
		r += self.n
		res = self.defaultvalue
		while l < r:
			if l & 1:
				res = self.func(res, self.segmentTree[l])
				l += 1
			l >>= 1
			if r & 1:
				r -= 1
				res = self.func(res, self.segmentTree[r])
			r >>= 1
		return res

	def update(self, i, value):
		i += self.n
		self.segmentTree[i] = value
		while i > 1:
			i >>= 1
			self.segmentTree[i] = self.func(self.segmentTree[2 * i], self.segmentTree[2 * i + 1])

class UnionFind:

	def __init__(self, n):
		self.n = n
		self.parents = list(range(n))

	def find(self, x):
		if self.parents[x] == x:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x != y:
			self.parents[x] = y
dire = [0, 1, 0, -1, 0]

def is_prime(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return True

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def case(t):
	print('Case #{}:'.format(t), end=' ')
RANDOM = random.randrange(2 ** 62)

def Wrapper(x):
	return x ^ RANDOM

def factors(n):
	if n == 0:
		return set()
	return set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))
MOD = 10 ** 9 + 7

def binpow(a, b):
	if b == 0:
		return 1
	res = binpow(a, b // 2)
	res = pow(res, 2, MOD)
	if b % 2:
		return res * a % MOD
	return res

def mod_inverse(a):
	return binpow(a, MOD - 2)
MAX = 2 * 10 ** 5 + 5

def solve():
	(n, x) = map(int, input().split())
	arr = list(map(int, input().split()))
	evencount = sum([1 for i in arr if i % 2 == 0])
	if x % 2 == 1:
		print(math.ceil(evencount / 2))
	elif evencount == n:
		print(-1)
	else:
		print(evencount)
for t in range(int(input())):
	solve()


import math
for _ in range(int(input())):
	(n, x) = map(int, input().split())
	arr = list(map(int, input().split()))
	(even, odd) = (0, 0)
	for i in arr:
		if i % 2 == 0:
			even += 1
		else:
			odd += 1
	if x & 1:
		print(math.ceil(even / 2))
	elif not odd:
		print(-1)
	else:
		print(even)


from math import sqrt, ceil, floor, gcd, log2
import sys
from sys import stdin, stdout
from collections import Counter, defaultdict, OrderedDict, deque
from itertools import combinations, groupby
from time import time
from heapq import heappop, heappush, heapify
t = int(input())
for _ in range(t):
	(n, x) = map(int, input().split())
	arr = list(map(int, input().split()))
	(o, e) = (0, 0)
	for i in range(n):
		if arr[i] % 2:
			o += 1
		else:
			e += 1
	if x % 2:
		if e % 2:
			print(e // 2 + 1)
		else:
			print(e // 2)
	elif o == 0:
		print(-1)
	else:
		print(e)


import math
T = int(input())
for i in range(T):
	(N, X) = map(int, input().split())
	A = list(map(int, input().split()))
	even_count = 0
	odd_count = 0
	for i in A:
		if i % 2 == 0:
			even_count += 1
		else:
			odd_count += 1
	if X % 2 != 0:
		print(math.ceil(even_count / 2))
	elif odd_count == 0:
		print('-1')
	else:
		print(even_count)


for k in range(int(input())):
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	even_count = 0
	for i in a:
		if i % 2 == 0:
			even_count += 1
	if x % 2 == 0:
		if even_count == n:
			print(-1)
		else:
			print(even_count)
	elif x % 2 != 0:
		print(even_count // 2) if even_count % 2 == 0 else print(even_count // 2 + 1)


import math
t = int(input())
for i in range(t):
	(n, x) = map(int, input().split())
	arr = list(map(int, input().split()))
	even_count = 0
	odd_count = 0
	for i in arr:
		if i % 2 == 0:
			even_count += 1
		else:
			odd_count += 1
	if x % 2 != 0:
		print(math.ceil(even_count / 2))
	elif odd_count == 0:
		print('-1')
	else:
		print(even_count)


import math
a = int(input(''))
for i in range(a):
	(N, X) = [int(x) for x in input('').split()]
	t = [int(x) for x in input('').split()]
	c = 0
	j = 0
	for j in t:
		if j % 2 == 0:
			c = c + 1
		else:
			j = j + 1
	if c > j and X % 2 == 0 or (c == N and X % 2 == 0):
		print(-1)
	elif X % 2 != 0:
		print(math.ceil(c / 2))
	else:
		print(c)


from functools import reduce
import math

def vout(v):
	print(' '.join(map(str, v)))

def main(is_testCases=True):
	testCases = 1
	if is_testCases:
		testCases = int(input())
	for _ in range(testCases):
		(n, x) = map(int, input().split())
		v = map(int, input().split())
		even = len(list(filter(lambda a: not a & 1, v)))
		odd = n - even
		if x & 1:
			print(math.ceil(even / 2.0))
		else:
			print(even if odd > 0 else -1)
main()


import math
t = int(input())
while t:
	(n, x) = input().split()
	n = int(n)
	x = int(x)
	l = [int(item) for item in input().split()]
	ev = 0
	for i in l:
		if i % 2 == 0:
			ev += 1
	od = n - ev
	if x % 2 != 0:
		print(math.ceil(ev / 2))
	elif ev == n:
		print(-1)
	else:
		print(ev)
	t = t - 1


import math
for i in range(int(input())):
	(n, x) = map(int, input().split())
	cnt_odd = sum((1 for a in map(int, input().split()) if a % 2 == 1))
	cnt_even = n - cnt_odd
	if cnt_even == 0:
		print(0)
		continue
	if x % 2 == 1:
		print(math.ceil(cnt_even / 2))
		continue
	if x % 2 == 0 and cnt_odd == 0:
		print(-1)
		continue
	print(cnt_even)


import math
case = int(input())
for _ in range(case):
	(n, x) = map(int, input().split(' '))
	arr = list(map(int, input().split(' ')))
	even = 0
	odd = 0
	for i in range(n):
		if arr[i] & 1 == 0:
			even += 1
		else:
			odd += 1
	if even == 0:
		print(0)
		continue
	if even == n and x & 1 == 0:
		print(-1)
		continue
	if x & 1 == 1:
		res = math.ceil(even / 2)
		print(res)
		continue
	if x & 1 == 0:
		print(even)


for t in range(int(input())):
	(n, x) = [int(i) for i in input().split()]
	ai = [int(i) for i in input().split()]
	count = 0
	for i in ai:
		if i % 2 == 0:
			count += 1
	print(int((count + 1) / 2) if x % 2 != 0 else -1 if count == n else count)


import math
for _ in range(int(input())):
	(N, X) = map(int, input().split())
	A = list(map(int, input().split()))
	(A_EVEN, A_ODD) = ([], [])
	for a in A:
		if a % 2 == 0:
			A_EVEN.append(a)
		else:
			A_ODD.append(a)
	num_ops = 0
	if not A_EVEN:
		print(num_ops)
	elif len(A_EVEN) == N:
		if X % 2 != 0:
			print(math.ceil(N / 2))
		else:
			print(-1)
	elif X % 2 != 0:
		print(math.ceil(len(A_EVEN) / 2))
	else:
		print(len(A_EVEN))


t = int(input())
while t > 0:
	(n, x) = input().split()
	(n, x) = (int(n), int(x))
	l = list(map(int, input().split()))
	count = 0
	for i in l:
		if i % 2 == 0:
			count += 1
	if x % 2 != 0:
		print(int((count + 1) / 2))
	elif count == n:
		print(-1)
	else:
		print(count)
	t = t - 1