An array $b$ is good if the sum of elements of $b$ is even.

You are given an array $a$ consisting of $n$ positive integers. In one operation, you can select an index $i$ and change $a_i := \lfloor \frac{a_i}{2} \rfloor$. $^\dagger$

Find the minimum number of operations (possibly $0$) needed to make $a$ good. It can be proven that it is always possible to make $a$ good.

$^\dagger$ $\lfloor x \rfloor$ denotes the floor function — the largest integer less than or equal to $x$. For example, $\lfloor 2.7 \rfloor = 2$, $\lfloor \pi \rfloor = 3$ and $\lfloor 5 \rfloor =5$.


-----Input-----

Each test contains multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 1000$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \leq n \leq 50$) — the length of the array $a$.

The second line of each test case contains $n$ space-separated integers $a_1,a_2,\ldots,a_n$ ($1 \leq a_i \leq 10^6$) — representing the array $a$.

Do note that the sum of $n$ over all test cases is not bounded.


-----Output-----

For each test case, output the minimum number of operations needed to make $a$ good.


-----Examples-----

Input
4
4
1 1 1 1
2
7 4
3
1 2 4
1
15
Output
0
2
1
4


-----Note-----

In the first test case, array $a$ is already good.

In the second test case, we can perform on index $2$ twice. After the first operation, array $a$ becomes $[7,2]$. After performing on index $2$ again, $a$ becomes $[7,1]$, which is good. It can be proved that it is not possible to make $a$ good in less number of operations.

In the third test case, $a$ becomes $[0,2,4]$ if we perform the operation on index $1$ once. As $[0,2,4]$ is good, answer is $1$.

In the fourth test case, we need to perform the operation on index $1$ four times. After all operations, $a$ becomes $[0]$. It can be proved that it is not possible to make $a$ good in less number of operations.

Source: codeforces | Difficulty: EASY
Tags: Number theory

Mathematics

Greedy algorithms


Solutions:
for s in [*open(0)][2::2]:
	a = (*map(int, s.split()),)
	print(sum(a) % 2 * min((len(x) - len(x.rstrip(x[-1])) for x in map(bin, a))))


t = int(input())
for test in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	s = sum(a)
	if s % 2 == 0:
		print(0)
	else:
		mx = 1000000
		for i in range(n):
			if a[i] % 2 != 0:
				q = bin(a[i])[2:]
				q = q[::-1] + '0'
				mx = min(mx, q.index('0'))
			else:
				q = bin(a[i])[2:]
				q = q[::-1]
				mx = min(mx, q.index('1'))
		print(mx)


t = int(input())
for x in range(t):
	n = int(input())
	nums = [int(i) for i in input().split(' ')]
	if sum(nums) % 2 == 0:
		print(0)
	else:
		for i in range(n):
			a = bin(nums[i])[:1:-1] + '0'
			if a[0] == '0':
				target = '1'
			else:
				target = '0'
			nums[i] = a.index(target)
		print(min(nums))


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	x = sum(l)
	if x % 2 == 0:
		print(0)
	else:
		l1 = []
		for i in l:
			p = bin(i)[2:]
			if i % 2 == 0:
				if '1' in p:
					x = p[::-1].index('1')
					l1.append(x)
				else:
					l1.append(len(p))
			elif '0' in p:
				x = p[::-1].index('0')
				l1.append(x)
			else:
				l1.append(len(p))
		print(min(l1))


t = int(input())
for _ in range(t):
	n = int(input())
	li = list(map(int, input().split()))
	su = sum(li)
	if su % 2 == 0:
		print(0)
	else:
		fi = []
		for i in li:
			p = bin(i)[2:]
			if i % 2 == 0:
				if '1' in p:
					x = p[::-1].index('1')
					fi.append(x)
				else:
					fi.append(len(p))
			elif '0' in p:
				x = p[::-1].index('0')
				fi.append(x)
			else:
				fi.append(len(p))
		print(min(fi))


t = int(input())

def run():
	n = int(input())
	lst = list(map(int, input().split()))
	sta = False
	min_ooe = 64
	for i in range(n):
		if lst[i] & 1:
			sta = not sta
			mid = lst[i] >> 1
			for j in range(min_ooe):
				if mid & 1:
					mid >>= 1
				else:
					min_ooe = min(j + 1, min_ooe)
					break
		else:
			mid = lst[i] >> 1
			for j in range(min_ooe):
				if mid & 1:
					min_ooe = min(j + 1, min_ooe)
					break
				else:
					mid >>= 1
	if sta:
		print(min_ooe)
	else:
		print(0)
while t:
	t -= 1
	run()


def test(x):
	s = bin(x)[::-1].replace('b', '')
	return min(s.index('01') if '01' in s else 100, s.index('10') if '10' in s else 100)
t = int(input())
for _ in range(t):
	n = input()
	a = list(map(int, input().split()))
	if sum(a) % 2 == 0:
		print(0)
		continue
	b = [test(x) for x in a]
	print(min(b) + 1)


import sys
input = lambda : sys.stdin.readline().rstrip()
t = int(input())
for i in range(t):
	n = int(input())
	ls = list(map(int, input().split()))
	if sum(ls) % 2 == 0:
		print('0')
	else:
		odd_l = []
		eve_l = []
		t1 = []
		t2 = []
		for i in ls:
			if i % 2 == 1:
				t1.append(i)
			else:
				t2.append(i)
		odd_l = list(set(t1))
		eve_l = list(set(t2))
		lo = len(odd_l)
		le = len(eve_l)
		res_o = [0] * lo
		res_e = [0] * le
		i = 0
		j = 0
		while True:
			odd_l[i] //= 2
			res_o[i] += 1
			if odd_l[i] % 2 == 0:
				res = res_o[i]
				break
			if i < lo - 1:
				i += 1
			else:
				i = 0
		while le != 0:
			eve_l[j] //= 2
			res_e[j] += 1
			if eve_l[j] % 2 == 1:
				res = min(res, res_e[j])
				break
			if j < le - 1:
				j += 1
			else:
				j = 0
		print(res)


from math import log2
for _ in ' ' * int(input()):
	n = int(input())
	x = list(map(int, input().split()))
	b = 1000001
	j = 0
	c = 1000001
	for a in x:
		if a % 2:
			b = min(int(log2(-a & a + 1)), b)
			j += 1
		else:
			c = min(c, int(log2(a & -a)))
	if j % 2 == 0:
		print(0)
		continue
	print(min(b, c))


import sys
import collections
from math import ceil, gcd, sqrt, log
import bisect
INF = float('inf')
mod = 1000000007

def solve():
	n = int(input())
	A = list(map(int, input().split()))
	odds = 0
	for i in A:
		if i % 2 == 1:
			odds += 1
	if odds % 2 == 0:
		print(0)
		return
	min_odd_bin = 32
	min_even_bin = 32
	for i in A:
		s = bin(i)[2:][::-1]
		count = 0
		if i % 2 == 1:
			for bit in s:
				if bit != '1':
					break
				else:
					count += 1
			if count < min_odd_bin:
				min_odd_bin = count
		else:
			for bit in s:
				if bit != '0':
					break
				else:
					count += 1
			if count < min_even_bin:
				min_even_bin = count
	ans = min(min_odd_bin, min_even_bin)
	print(ans)
t = int(input())
while t != 0:
	solve()
	t -= 1


for _ in range(int(input())):
	n = int(input())
	num = list(map(int, input().split()))
	if sum(num) % 2 == 0:
		print(0)
		continue
	ans = 10000000
	for i in range(n):
		if num[i] % 2 != 0:
			x = bin(num[i])[2:]
			x = x[::-1]
			if '0' in x:
				ans = min(ans, x.find('0'))
			else:
				ans = min(ans, len(x))
		else:
			x = bin(num[i])[2:]
			x = x[::-1]
			ans = min(ans, x.find('1'))
	print(ans)


import sys
input = sys.stdin.readline
import math

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

def print_number(number):
	print_str_line(f'{number}')

def ans(nums):
	sum_nums = sum(nums)
	if sum_nums % 2 == 0:
		return 0
	min_operations = 2 ** 32
	for num in nums:
		curr_operations = 0
		if num % 2 == 1:
			while num % 2 == 1:
				curr_operations += 1
				num //= 2
		else:
			while num % 2 != 1:
				curr_operations += 1
				num //= 2
		min_operations = min(min_operations, curr_operations)
	return min_operations
number_of_inputs = int(input())
for i in range(number_of_inputs):
	nums_len = int(input())
	nums = [int(num) for num in input().split(' ')]
	_ans = ans(nums)
	print_number(_ans)


import sys
input = sys.stdin.readline

def check(a):
	for i in a:
		if i - i // 2 & 1:
			return True
	return False

def f():
	n = int(input())
	a = [*map(int, input().split())]
	s = sum(a)
	odds = []
	if s & 1 == 0:
		return 0
	ans = 1
	a.sort()
	x = 0
	while not check(a):
		for i in range(n):
			a[i] >>= 1
		ans += 1
	return ans
for case in range(int(input())):
	print(f())


def number():
	return list(map(int, input().split()))

def str():
	return list(input().split())

def check(arr):
	c = 1
	min = 20
	for x in arr:
		c = 0
		if x % 4 == 1 or x % 4 == 2:
			return 1
		else:
			t = x
			p = x % 2
			while True:
				t = t // 2
				n = t % 2
				c += 1
				if n != p:
					if min > c:
						min = c
					break
	return min
y = number()
while y[0] > 0:
	num = number()
	n = num[0]
	arr = number()
	s = sum(arr)
	if s % 2 == 0:
		print(0)
		y[0] -= 1
		continue
	print(check(arr))
	y[0] -= 1


from sys import stdin
input = stdin.readline

def divideAndConquer(num, Arr):
	if sum(Arr) % 2 == 0:
		print(0)
		return
	min_ = 10 ** 6 + 1
	for elem in Arr:
		c = 0
		if elem % 2:
			while elem % 2:
				elem //= 2
				c += 1
		else:
			while not elem % 2:
				elem //= 2
				c += 1
		min_ = min(min_, c)
	print(min_)
for i in range(int(input())):
	n = int(input())
	L = [*map(int, input().split())]
	divideAndConquer(n, L)


import sys
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
test_cases = inp()
inp_arr = []
for i in range(test_cases):
	num = inp()
	nums = inlt()
	inp_arr.append(nums)

def findResult(nums):
	if sum(nums) % 2 == 0:
		return 0
	result = float('inf')
	for num in nums:
		count = 0
		isEven = num % 2 == 0
		while (num % 2 == 0) == isEven:
			num = num // 2
			count += 1
		result = min(result, count)
	return result
result = [findResult(cheeses) for cheeses in inp_arr]
for m in result:
	print(m)


def solve():
	n = int(input())
	s = input()
	a = s.split(' ')
	a = [int(x) for x in a]
	opt = float('inf')
	c = 0
	for x in a:
		if x % 2:
			c += 1
	if c % 2 == 0:
		print(0)
		return
	for x in a:
		r = x % 2
		y = x // 2
		l = 1
		while y % 2 == r:
			y //= 2
			l += 1
		opt = min(opt, l)
	print(opt)
	return
t = int(input())
for _ in range(t):
	solve()


count = 0
(output, countlist) = ([], [])
t = int(input())
for i in range(t):
	length = int(input())
	l = list(map(int, input().split()))
	lbin = [bin(i) for i in l]
	if sum(l) % 2 == 0:
		output.append(0)
	else:
		for i in lbin:
			j = '0' + i[2:]
			j = ''.join(reversed(j))
			if j[0] == '0':
				count = j.find('1')
			elif j[0] == '1':
				count = j.find('0')
			countlist.append(count)
		output.append(min(countlist))
		countlist = []
for i in output:
	print(i)


def solve(lst):
	if sum(lst) % 2 == 0:
		return 0
	else:
		least_count = float('inf')
		for number in lst:
			count = 0
			if number % 2 == 1:
				while number % 2 != 0:
					number //= 2
					count += 1
				if count < least_count:
					least_count = count
				if least_count == 1:
					break
			else:
				while number % 2 != 1:
					number //= 2
					count += 1
				if count < least_count:
					least_count = count
				if least_count == 1:
					break
		return least_count
t = int(input())
for _ in range(t):
	n = int(input())
	lst = list(map(int, input().split()))
	print(solve(lst))


def c(n):
	if n % 2:
		n += 1
	k = 0
	while n % 2 == 0:
		k += 1
		n //= 2
	return k
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	s = sum(a)
	if s % 2:
		print(min(list(map(c, a))))
	else:
		print(0)


def oddOperation(a):
	nb = 0
	while a % 2 != 0:
		a = a // 2
		nb += 1
	return nb

def evenOperatin(a):
	nb = 0
	while a % 2 != 1:
		a = a // 2
		nb += 1
	return nb
t = int(input())
result = []
for i in range(t):
	operations = []
	n = int(input())
	ai = list(map(int, input().split(' ')))
	if sum(ai) % 2 == 0:
		result.append(0)
	else:
		for j in ai:
			if j % 2 == 0:
				operations.append(evenOperatin(j))
			else:
				operations.append(oddOperation(j))
		result.append(min(operations))
for i in result:
	print(i)


import math
import collections

def power2(n):
	x = 0
	if n % 2 == 0:
		while n % 2 == 0:
			x += 1
			n = n // 2
	else:
		while n % 2 == 1:
			x += 1
			n = n // 2
	return x
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	sum = 0
	for i in l:
		sum += i
	if sum % 2 == 0:
		print(0)
		continue
	else:
		ans = math.inf
		for j in l:
			ans = min(ans, power2(j))
		print(ans)


def func(n, z):
	ret = 0
	while n % 2 == z:
		n //= 2
		ret += 1
	return ret
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	if sum(a) % 2 == 0:
		print(0)
		continue
	ans = 1000000000
	for val in a:
		ans = min(ans, func(val, val % 2))
	print(ans)


def ans(arr):
	s = sum(arr)
	if s % 2 == 0:
		return 0
	c = 2147483648
	for i in arr:
		l = 0
		t = i
		if t % 2:
			while t > 0 and t % 2:
				t = t // 2
				l += 1
		else:
			while t > 0 and t % 2 == 0:
				t = t // 2
				l += 1
		c = min(c, l)
	return c
for _ in range(int(input())):
	n = int(input())
	arr = [int(i) for i in input().split()]
	print(ans(arr))


def convertToEven(n) -> int:
	c = 0
	while n % 2 != 0:
		c += 1
		n //= 2
	return c

def convertToOdd(n) -> int:
	c = 0
	while n % 2 != 1:
		c += 1
		n //= 2
	return c

def solve():
	n = int(input())
	nums = list(map(int, input().split()))
	even = []
	odd = []
	for num in nums:
		if num % 2 == 0:
			even.append(num)
		else:
			odd.append(num)
	if len(odd) % 2 == 0:
		print(0)
		return
	choice1 = list(map(convertToEven, odd))
	choice2 = list(map(convertToOdd, even))
	best1 = min(choice1) if len(choice1) > 0 else float('inf')
	best2 = min(choice2) if len(choice2) > 0 else float('inf')
	print(min(best1, best2))
	return
T = int(input())
for _ in range(T):
	solve()


def count_2(ele):
	count = 0
	while ele > 0:
		ele = ele // 2
		count += 1
		if ele % 2 == 0:
			return count
	return count

def count_1(ele):
	count = 0
	while ele >= 1:
		ele = ele // 2
		count += 1
		if ele % 2 == 1:
			return count
	return count
t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	if sum(arr) % 2 == 0:
		print(0)
	else:
		mini = float('inf')
		for i in range(n):
			if arr[i] % 2 == 1:
				num = count_2(arr[i])
			else:
				num = count_1(arr[i])
			if num < mini:
				mini = num
		print(mini)


import math

def powerof2(n):
	ans = 0
	if n % 2 == 0:
		while n % 2 == 0:
			ans = ans + 1
			n = n // 2
	else:
		k = n + 1
		n = k
		while n % 2 == 0:
			ans = ans + 1
			n = n // 2
	return ans
t = int(input())
for i in range(0, t):
	n = int(input())
	a = list(map(int, input().split()))
	sumi = 0
	ans = int(math.log(pow(10, 6), 2) + 7)
	for j in range(0, n):
		sumi = sumi + a[j]
		ans = min(ans, powerof2(a[j]))
	if sumi % 2 == 0:
		print(0)
	else:
		print(int(ans))


def half(arr, n):
	for i in range(n):
		if arr[i] % 2 != arr[i] // 2 % 2:
			return True
t = int(input())
for _ in range(t):
	n = int(input())
	arr = [int(x) for x in input().split()]
	sum = 0
	steps = 1
	for i in arr:
		sum += i
	if sum % 2 == 0:
		print(0)
	else:
		while not half(arr, n):
			arr_ = [x // 2 for x in arr]
			steps += 1
			arr = arr_
		print(steps)


def f(num):
	prev = num % 2
	count = 0
	while num % 2 == prev:
		num //= 2
		count += 1
	return count
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	if sum(arr) % 2 == 0:
		print(0)
	else:
		count = float('inf')
		for i in arr:
			count = min(count, f(i))
		print(count)


import sys

def cal(x):
	ans = 0
	if x % 2 == 0:
		while x % 2 == 0:
			x //= 2
			ans += 1
	else:
		while x % 2 != 0:
			x //= 2
			ans += 1
	return ans

def solve():
	input = sys.stdin.readline
	n = int(input())
	arr = list(map(int, input().split()))
	(odd, even) = (0, 0)
	(minToOdd, minToEven) = (float('inf'), float('inf'))
	for i in range(n):
		if arr[i] % 2 == 0:
			even += 1
			minToEven = min(minToEven, cal(arr[i]))
		else:
			odd += 1
			minToOdd = min(minToOdd, cal(arr[i]))
	if odd % 2 == 0:
		print(0)
	else:
		print(min(minToOdd, minToEven))

def main():
	t = int(input())
	for _ in range(t):
		solve()
main()


def solve(n, arr):

	def ln(n):
		tot = 0
		if n & 1:
			while n & 1:
				n //= 2
				tot += 1
		else:
			while not n & 1:
				n //= 2
				tot += 1
		return tot
	if sum(arr) % 2 == 0:
		return 0
	res = float('inf')
	for i in arr:
		res = min(res, ln(i))
	return res
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	print(solve(n, arr))


def least_odd(n):
	count = 0
	while n % 2 == 1:
		n = n // 2
		count = count + 1
	return count

def least_even(n):
	count = 0
	while n % 2 == 0:
		n = n // 2
		count = count + 1
	return count
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	sum = 0
	l = []
	for i in range(n):
		l.append(0)
	for i in range(n):
		sum = sum + a[i]
		if a[i] % 2 == 0:
			l[i] = least_even(a[i])
		else:
			l[i] = least_odd(a[i])
	if sum % 2 == 0:
		print(0)
	else:
		print(min(l))


import math

def f(L):
	s = sum(L)
	n = len(L)
	c = math.inf
	if s % 2 == 0:
		return 0
	else:
		S = []
		P = []
		for i in range(n):
			if L[i] % 2 == 1:
				S.append(L[i])
			else:
				P.append(L[i])
		for j in S:
			x = j
			w = 0
			while x % 2 != 0:
				x = x // 2
				w += 1
			if c >= w:
				c = w
		for l in P:
			b = l
			e = 0
			while b % 2 != 1:
				b = b // 2
				e += 1
			if c >= e:
				c = e
	return c
x = int(input())
for i in range(x):
	o = int(input())
	x = list(map(int, input().split()))
	print(f(x))


def miss(m):
	s = 1
	if m % 2 == 0:
		while True:
			m = m // 2
			if m % 2 != 0:
				break
			s += 1
	else:
		while True:
			m = m // 2
			if m % 2 == 0:
				break
			s += 1
	return s
for _ in range(int(input())):
	x = int(input())
	ls = [int(y) for y in input().split()]
	if sum(ls) % 2 == 0:
		print(0)
	else:
		s = ls[0]
		for i in range(x):
			a = miss(ls[i])
			if a < s:
				s = a
		print(s)


t = int(input())
for _ in range(t):
	n = int(input())
	lst = list(map(int, input().split()))
	if sum(lst) % 2 == 0:
		print(0)
		continue
	else:
		oper = 1000000
		for x in lst:
			op = 0
			tmp = x % 2
			while True:
				x //= 2
				op += 1
				if x % 2 != tmp:
					break
			if op < oper:
				oper = op
		print(oper)


from math import inf, isinf

def test(s):
	c = 0
	if s % 2 == 0:
		while s % 2 == 0:
			s //= 2
			c += 1
	else:
		while s % 2 != 0:
			s //= 2
			c += 1
	return c

def solve():
	input()
	s = tuple(sorted((int(x) for x in input().split())))
	if sum(s) % 2 == 0:
		print(0)
	else:
		min_ = inf
		for item in s:
			min_ = min(min_, test(item))
		print(min_)
for _ in range(int(input())):
	solve()


def solution():
	n = int(input())
	a = [int(num) for num in input().split()]
	if sum(a) % 2 == 0:
		print(0)
		return
	good = False
	ans = 0
	while not good:
		ans += 1
		for i in range(n):
			prev = a[i]
			a[i] //= 2
			if prev % 2 ^ a[i] % 2:
				good = True
				break
	print(ans)

def main():
	t = int(input())
	while t:
		solution()
		t -= 1
main()


def ans(arr):
	if sum(arr) % 2 == 0:
		return 0
	else:
		odd = []
		even = []
		for x in arr:
			if x % 2:
				odd.append(x)
			else:
				even.append(x)
		min_e = 10 ** 7
		for x in even:
			k = 0
			while x != 1:
				x //= 2
				k += 1
				if x % 2:
					break
			min_e = min(min_e, k)
		min_o = 10 ** 7
		for x in odd:
			k = 0
			while x != 0:
				x //= 2
				k += 1
				if x % 2 == 0:
					break
			min_o = min(min_o, k)
		return min(min_o, min_e)
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	print(ans(a))


from math import floor

def make_good(a):
	cnt = 0
	(odd_set, even_set) = (set(), set())
	for i in a:
		if i % 2 != 0:
			cnt += 1
			odd_set.add(i)
		else:
			even_set.add(i)
	if cnt % 2 == 0:
		return 0
	(make_odd_map, make_even_map) = ({}, {})
	for i in odd_set:
		cnt = 0
		temp_i = i
		while i % 2 != 0:
			i = floor(i // 2)
			cnt += 1
		make_odd_map[temp_i] = cnt
	for i in even_set:
		cnt = 0
		temp_i = i
		while i % 2 == 0:
			i = floor(i // 2)
			cnt += 1
		make_odd_map[temp_i] = cnt
	return min(list(make_even_map.values()) + list(make_odd_map.values()))
test_cnt = int(input().strip())
for _ in range(test_cnt):
	_ = input()
	a = [int(i) for i in input().strip().split()]
	print(make_good(a))


def count_chg(number):
	if number == 1:
		return 1
	bin_str = str(bin(number)[2:])
	last_num = 1
	for i in range(1, len(bin_str)):
		if bin_str[-1 - i] == bin_str[-1]:
			last_num += 1
		else:
			break
	return last_num

def number_change(inp):
	list_num = list(map(int, inp.split(' ')))
	if sum(list_num) % 2 == 0:
		print(0)
	else:
		chg_list = [count_chg(num) for num in list_num]
		print(min(chg_list))
counts = int(input())
for i in range(counts):
	length = int(input())
	number_change(input())


def val1(k):
	d = 0
	while k % 2 == 0:
		k //= 2
		d += 1
	return d

def val2(k):
	d = 0
	while k % 2 != 0:
		k //= 2
		d += 1
	return d
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	count = sum(a)
	count1 = 0
	count2 = 22
	if count % 2 != 0:
		for k in a:
			if k % 2 == 0:
				b = val1(k)
				if b < count2:
					count2 = b
					count1 = count2
			elif k % 2 != 0:
				b = val2(k)
				if b < count2:
					count2 = b
					count1 = count2
	print(count1)


for i in range(int(input())):
	n = int(input())
	a = sorted(list(map(int, input().split())))
	if sum(a) % 2 == 0:
		print(0)
	else:
		a = list(set(a))
		count = None
		for k in a:
			j = k
			x = 0
			if j % 2 == 0:
				while j % 2 == 0:
					j //= 2
					x += 1
			else:
				while j % 2 != 0:
					j //= 2
					x += 1
			if count == None or count > x:
				count = x
		print(count)


from typing import List
t = int(input())

def solve(a: List[int]):
	s = sum(a)
	if s & 1 == 0:
		return 0
	min_count = float('inf')
	for num in a:
		if num & 1 == 1:
			count = 0
			while num & 1 == 1:
				count += 1
				num //= 2
			min_count = min(min_count, count)
		else:
			count = 0
			while num & 1 == 0:
				count += 1
				num //= 2
			min_count = min(min_count, count)
	return min_count
while t > 0:
	n = int(input())
	a = [int(num) for num in input().split(' ', n - 1)]
	ans = solve(a)
	print(ans)
	t -= 1


from functools import reduce
import math

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

def vin(datatype):
	return list(map(datatype, input().split()))

def Filter(a, b):
	return list(filter(a, b))

def Map(a, b):
	return list(map(a, b))

def main(is_testCases=True):
	testCases = 1
	if is_testCases:
		testCases = int(input())
	for _ in range(testCases):
		n = int(input())
		v = vin(int)

		def check(element):
			ans = 0
			parity = element & 1
			while element:
				ans += 1
				element //= 2
				if parity != element & 1:
					return ans
		answer = Map(check, v)
		print(min(answer) if reduce(lambda a, b: a + b, v) & 1 else 0)
main()


T = int(input())
for _ in range(T):
	n = int(input())
	a = list(map(int, input().split()))
	ans = 10 ** 8
	res = sum(a)
	if res & 1:
		for item in a:
			tmp = 0
			if item & 1:
				while item & 1:
					item >>= 1
					tmp += 1
				ans = min(ans, tmp)
			else:
				while item > 0 and (not item & 1):
					item >>= 1
					tmp += 1
				ans = min(ans, tmp)
	else:
		ans = 0
	print(ans)


from typing import List
from bisect import *
from collections import *
from functools import *
from itertools import *
from math import *
from queue import PriorityQueue
INF = 2 ** 64 - 1
MOD = 10 ** 9 + 7
mi = lambda : map(int, input().split())
li = lambda : list(mi())

def main(n, nums):
	s = sum(nums)
	if s % 2 == 0:
		print(0)
		return
	ans = INF
	for v in nums:
		temp = 0
		if v % 2 == 0:
			while v % 2 == 0 and v > 0:
				v = v // 2
				temp += 1
		else:
			while v % 2 == 1 and v > 0:
				v = v // 2
				temp += 1
		ans = min(ans, temp)
	print(ans)
	return
caseNum = int(input())
for i in range(0, caseNum):
	n = int(input())
	nums = li()
	main(n, nums)


import math
from collections import Counter

def li():
	return list(map(int, input().split()))

def nt():
	return int(input())

def st():
	return input()
yes = 'YES'
no = 'NO'
even = 'EVEN'
odd = 'ODD'

def prefix(L):
	size = len(L)
	for i in range(1, size):
		L[i] = L[i] + L[i - 1]
	return L

def process(x):
	count = 0
	if x % 2 == 0:
		while x % 2 == 0:
			count += 1
			x //= 2
	else:
		while x % 2 == 1:
			count += 1
			x //= 2
	return count
for _ in range(int(input())):
	size = nt()
	L = li()
	s = sum(L)
	if s % 2 == 0:
		print(0)
		continue
	ans = 3100
	for i in range(size):
		temp = process(L[i])
		if temp < ans:
			ans = temp
	print(ans)


def binary(num):
	cnt = 0
	if num % 2 == 0:
		while num % 2 == 0:
			cnt += 1
			num = num // 2
	else:
		while num % 2 == 1:
			cnt += 1
			num = num // 2
	return cnt
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split(sep=' ')))
	b = []
	sum = 0
	for j in range(n):
		sum += a[j]
	if sum % 2 == 0:
		print(0)
	else:
		for j in range(n):
			b.append(binary(a[j]))
		print(min(b))


test_case = int(input())
for test in range(test_case):
	length = int(input())
	List = list(map(int, input().split()))
	odd_list = []
	even_list = []
	for i in List:
		if i % 2 == 0:
			even_list.append(i)
		else:
			odd_list.append(i)
	odd = len(odd_list)
	even = len(even_list)
	if odd % 2 == 0:
		print(0)
	else:
		ans = float('inf')
		for i in odd_list:
			c = 0
			while i % 2 != 0:
				i = i // 2
				c += 1
			ans = min(ans, c)
		for i in even_list:
			c = 0
			while i % 2 == 0:
				i = i // 2
				c += 1
			ans = min(ans, c)
		print(ans)


import sys
input = sys.stdin.readline
T = int(input())
for _ in range(T):
	n = int(input())
	a = list(map(int, input().split()))
	asum = sum(a)
	if asum % 2 == 0:
		print(0)
		continue
	if 1 in a or 2 in a:
		print(1)
		continue
	m = []
	for i in a:
		x = i % 2
		c = 0
		while 1:
			i //= 2
			c += 1
			if i % 2 != x:
				m.append(c)
				break
	print(min(m))


def solve():
	n = int(input())
	a = list(map(int, input().split()))
	s = sum(a)
	if s % 2 == 0:
		print(0)
		return
	ans = 10 ** 9
	for i in a:
		m = 1
		b = bin(i)[::-1]
		k = len(b)
		for j in range(1, k):
			if b[j] != b[j - 1]:
				break
			m += 1
		ans = min(ans, m)
	print(ans)
t = int(input())
for i in range(t):
	solve()


import math

def form(num):
	count = 0
	while True:
		if num % 2 == 0:
			return count
		num = num // 2
		count += 1
	return count

def form2(num):
	count = 0
	while True:
		if num % 2 == 1:
			return count
		num = num // 2
		count += 1
	return count
for i in range(int(input())):
	n = int(input())
	b = [int(x) for x in input().split()]
	even = []
	odd = []
	ans = 87298312873512653
	if sum(b) % 2 == 0:
		print(0)
		continue
	for i in b:
		if i % 2 == 0:
			ans = min(ans, form2(i))
		else:
			ans = min(ans, form(i))
			odd.append(i)
	o = form(min(odd))
	print(min(o, ans))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if sum(a) % 2 == 0:
		print(0)
	elif 1 in a:
		print(1)
	else:
		for x in a:
			flag = False
			if x % 4 == 1 or x % 4 == 2:
				print(1)
				flag = True
				break
		if flag:
			continue
		ans = 10 ** 10
		for x in a:
			if x % 2 == 0:
				y = x
				cnt = 0
				while y % 2 == 0:
					y //= 2
					cnt += 1
			else:
				y = x
				cnt = 0
				while y % 2 == 1:
					y //= 2
					cnt += 1
			ans = min(ans, cnt)
		print(ans)


t = int(input())

def solve(n, nums):
	total = sum(nums)
	ans = float('inf')
	if total & 1:
		for num in nums:
			(curr, now) = (num, 0)
			while not curr + num & 1:
				now += 1
				curr //= 2
			ans = min(ans, now)
	else:
		ans = 0
	return ans
for i in range(t):
	n = int(input())
	nums = list(map(int, input().split()))
	print(solve(n, nums))


def val1(num):
	op = 0
	while num % 2 == 0:
		num = num // 2
		op += 1
	return op

def val2(num):
	op = 0
	while num % 2 != 0:
		num = num // 2
		op += 1
	return op
T = int(input())
for t in range(0, T):
	n = int(input())
	arr = list(map(int, input().split(' ')))
	s = sum(arr)
	ans = 0
	mini = 22
	if s % 2 != 0:
		for item in arr:
			if item % 2 == 0:
				x = val1(item)
				if x < mini:
					mini = x
					ans = mini
			elif item % 2 != 0:
				x = val2(item)
				if x < mini:
					mini = x
					ans = mini
	print(ans)


def bbb(a, b):
	c = 0
	while a % 2 == b:
		c += 1
		a //= 2
	return c
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	count1 = 0
	m = 100
	for i in a:
		m = min(m, bbb(i, i % 2))
		if i % 2 == 1:
			count1 += 1
	if count1 % 2 == 1:
		print(m)
	else:
		print(0)


import sys

def solve(res):
	c = 1
	while (res - res // 2) % 2 == 0:
		c += 1
		res = res // 2
	return c
for _ in range(int(input())):
	res = sys.maxsize
	n = int(input())
	l = list(map(int, input().split()))
	if sum(l) % 2 == 0:
		print(0)
	else:
		for i in l:
			c = solve(i)
			if c == 1:
				res = 1
				break
			else:
				res = min(c, res)
		print(res)


from collections import *
import math

def solve():
	n = int(input())
	arr = list(map(int, input().split()))
	p = sum(arr)
	if p % 2 == 0:
		print(0)
	else:
		count = math.inf
		for i in arr:
			if i % 2 == 0:
				t = 0
				while i % 2 == 0:
					t += 1
					i //= 2
				count = min(count, t)
			elif i % 2 == 1:
				t = 0
				while i % 2 == 1:
					t += 1
					i //= 2
				count = min(count, t)
		print(count)
t = int(input())
for i in range(1, t + 1):
	solve()


def divisions_till_change(num):
	parity = num & 1
	counter = 0
	while num != 0:
		num >>= 1
		counter += 1
		if num & 1 != parity:
			return counter
	return 4294967295
tests = int(input())
for _ in range(tests):
	n = int(input())
	arr = list(map(int, input().split()))
	odd = 0
	for a in arr:
		odd ^= a & 1
	if not odd:
		print(0)
		continue
	print(min([divisions_till_change(a) for a in arr]))


import math
t = int(input())

def f(n):
	cnt = 0
	if n % 2 == 0:
		while n % 2 == 0:
			cnt += 1
			n /= 2
	else:
		while n % 2 != 0:
			cnt += 1
			n //= 2
	return cnt
while t:
	t -= 1
	n = int(input())
	lst = list(map(int, input().split()))
	if sum(lst) % 2 == 0:
		print(0)
	else:
		mn = 10 ** 7
		for i in lst:
			mn = min(f(i), mn)
		print(mn)


import sys

def checkEven(n):
	oper = 0
	while n % 2 == 0:
		n = n // 2
		oper += 1
	return oper

def checkOdd(n):
	oper = 0
	while n % 2 != 0:
		n = n // 2
		oper += 1
	return oper
t = int(input())
for ts in range(t):
	n = int(input())
	arr = input()
	arr = list(map(int, arr.split()))
	odd = []
	s = 0
	even = []
	for a in arr:
		s += a
	if s % 2 != 0:
		oper = sys.maxsize
		for a in arr:
			if a % 2 != 0:
				oper = min(oper, checkOdd(a))
			else:
				oper = min(oper, checkEven(a))
		print(oper)
	else:
		print(0)


def mindiv(z):
	c = 0
	if z % 2 == 1:
		while z % 2 != 0:
			z //= 2
			c += 1
		return c
	else:
		while z % 2 != 1:
			z //= 2
			c += 1
		return c
for tc in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if sum(a) % 2 == 0:
		print(0)
	else:
		d = []
		for i in range(n):
			d.append(mindiv(a[i]))
		d.sort()
		for i in range(n):
			if d[i] == 0:
				continue
			else:
				print(d[i])
				break


import sys
for i in range(int(input())):
	s = int(input())
	l = list(map(int, input().split()))
	(ol, ev) = ([], [])
	for i in l:
		if i % 2 == 0:
			ev.append(i)
		else:
			ol.append(i)
	if len(ol) % 2 == 0:
		print(0)
	else:
		ans1 = 10000001
		for j in ol:
			c = 0
			p = j
			while p % 2 != 0:
				p = p // 2
				c += 1
			ans1 = min(ans1, c)
		ans2 = 10000001
		for j in ev:
			c = 0
			p = j
			while p % 2 != 1:
				p = p // 2
				c += 1
			ans2 = min(ans2, c)
		if len(ev) == 0 or len(ol) == 0:
			print(min(ans1, ans2))
		else:
			print(min(ans1, ans2))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	s = sum(a)
	c = 10000000
	if s % 2 != 0:
		for x in a:
			t = 0
			if x % 2 == 0:
				while x % 2 == 0:
					t += 1
					x = x // 2
			else:
				while x % 2 != 0:
					t += 1
					x = x // 2
			c = min(c, t)
	if s % 2 == 0:
		print(0)
	else:
		print(c)


from math import log2

def depth_e(x):
	d = 0
	while x % 2 == 0:
		x //= 2
		d += 1
	return d

def depth_o(x):
	d = 0
	while x % 2 != 0:
		x //= 2
		d += 1
	return d
for t in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	e = 0
	o = 0
	min_e = 10 ** 9
	ans = 10 ** 9
	for i in range(n):
		if a[i] % 2 == 0:
			e += 1
			ans = min(depth_e(a[i]), ans)
		else:
			o += 1
			ans = min(depth_o(a[i]), ans)
	if o % 2 == 0:
		print(0)
	else:
		print(ans)


tests = int(input())
for _ in range(tests):
	m = int(input())
	n = list(map(int, input().split()))
	if not sum(n) & 1:
		print(0)
	else:
		res = 100
		for c in n:
			tmp = 0
			if c & 1:
				while c & 1:
					tmp += 1
					c >>= 1
			else:
				while not c & 1:
					tmp += 1
					c >>= 1
			res = min(res, tmp)
			if res == 1:
				break
		print(res)


import sys
t = int(sys.stdin.readline())
for i in range(t):
	n = int(input())
	lst = list(map(int, input().split()))
	ev = 0
	od = 0
	for j in lst:
		if j % 2 == 0:
			ev += 1
		else:
			od += 1
	ma = []
	if od % 2 != 0:
		for h in lst:
			if h % 2 != 0:
				ele = h
				c = 0
				while True:
					if ele % 2 == 0:
						break
					c += 1
					ele = ele // 2
				ma.append(c)
		for h in lst:
			if h % 2 == 0:
				ele = h
				c = 0
				while True:
					if ele % 2 != 0:
						break
					c += 1
					ele = ele // 2
				ma.append(c)
	if ma == []:
		print(0)
	else:
		print(min(ma))


import sys
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s.strip())

def invr():
	return map(int, input().split())
for _ in range(inp()):
	n = inp()
	arr = inlt()
	mn = 100000000
	for i in arr:
		val = i % 2
		c = 0
		while i != 0 and i % 2 == val:
			i //= 2
			c += 1
		mn = min(c, mn)
	if sum(arr) % 2 != 0:
		print(mn)
	else:
		print(0)


import math as mt
MAXN = 10001

def sieve():
	for i in range(4, MAXN, 2):
		spf[i] = 2
	for i in range(3, mt.ceil(mt.sqrt(MAXN))):
		if spf[i] == i:
			for j in range(i * i, MAXN, i):
				if spf[j] == j:
					spf[j] = i

def getFactorization(x):
	d = {}
	while x != 1:
		if spf[x] in d:
			d[spf[x]] += 1
		else:
			d[spf[x]] = 1
		x = x // spf[x]
	return d
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().strip().split()))
	if sum(a) % 2 == 0:
		print(0)
	else:
		c = 10000000
		for i in a:
			x = i
			xc = x % 2
			tc = 0
			while x % 2 != 1 - xc:
				tc += 1
				x = x // 2
			c = min(tc, c)
		print(c)


t = int(input())

def countodd(el):
	res = 0
	while el % 2 != 0:
		res += 1
		el //= 2
	return res

def counteven(el):
	res = 0
	while el > 0 and el % 2 != 1:
		res += 1
		el //= 2
	return res
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	if sum(arr) % 2 == 0:
		print(0)
		continue
	res = float('inf')
	for el in arr:
		if el & 1:
			res = min(res, countodd(el))
		else:
			res = min(res, counteven(el))
	print(res)


def solve(arr, n):
	summ = 0
	for i in range(n):
		summ += arr[i]
	if summ % 2 == 0:
		return 0
	ans = 100000000
	for i in range(n):
		parr = arr[i] % 2
		parrnew = parr
		anp = 0
		while parr == parrnew:
			arr[i] = arr[i] // 2
			anp += 1
			parrnew = arr[i] % 2
		ans = min(ans, anp)
	return ans
for _ in range(int(input())):
	n = int(input())
	arr = [int(x) for x in input().split()]
	print(solve(arr, n))


def findeven(n):
	c = 0
	while n > 0:
		n = n // 2
		c += 1
		if n % 2 == 0:
			return c
	return c

def findodd(n):
	c = 0
	while n > 0:
		n = n // 2
		c += 1
		if n % 2 != 0:
			return c
	return c
t = int(input())
for _ in range(t):
	n = int(input())
	l = [int(x) for x in input().split()]
	even = 0
	odd = 0
	o = []
	e = []
	for i in l:
		if i % 2 == 0:
			even += 1
			e.append(i)
		else:
			odd += 1
			o.append(i)
	if odd % 2 == 0:
		print(0)
	else:
		odd = odd % 2
		count = []
		for i in o:
			count.append(findeven(i))
		for i in e:
			count.append(findodd(i))
		count.sort()
		print(sum(count[:odd]))


for aa in range(int(input())):
	n = int(input())
	li = list(map(int, input().split()))
	c = 0
	if sum(li) % 2 == 0:
		print(0)
		continue
	p = []
	for i in li:
		if i % 2 == 0:
			c = 1
			while i // 2 % 2 == 0:
				i = i // 2
				c += 1
			p.append(c)
		elif i // 2 % 2 == 0:
			i = i // 2
			p.append(1)
		else:
			c = 1
			while i // 2 % 2 != 0:
				i = i // 2
				c += 1
			p.append(c)
	print(min(p))


def fuck(x):
	c = 0
	if x % 2 == 0:
		while x % 2 == 0:
			x = x // 2
			c += 1
	else:
		while x % 2 != 0:
			x = x // 2
			c += 1
	return c

def exe():
	if sum(lst) % 2 == 0:
		return 0
	return min([fuck(i) for i in lst])
for _ in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	print(exe())


for _ in range(int(input())):
	a = int(input())
	lt = list(map(int, input().split()))
	sm = sum(lt)
	if sm % 2 == 0:
		print(0)
		continue
	l2 = []
	for x in lt:
		bval = True
		if x % 2 == 0:
			bval = False
		temp = bin(x)[::-1]
		for y in range(len(temp) - 2):
			if bval and temp[y] == '0':
				l2.append(y)
				break
			elif not bval and temp[y] == '1':
				l2.append(y)
				break
		if bval:
			l2.append(len(temp) - 2)
	print(min(l2))


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	lo = []
	c = 0
	if sum(l) % 2 == 0:
		print('0')
	else:
		for i in l:
			if i % 2 == 1:
				s = i
				while s % 2 != 0:
					s //= 2
					c += 1
				lo.append(c)
				c = 0
			else:
				p = i
				while p % 2 != 1:
					p //= 2
					c += 1
				lo.append(c)
				c = 0
		print(min(lo))


def check(a, b):
	if a % 4 == 1:
		return b
	return check(a // 2, b + 1)

def check2(a, b):
	if a % 2 == 1:
		return b
	return check2(a // 2, b + 1)
for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	b = 0
	for i in a:
		b += i
	if b % 2 == 0:
		print('0')
		continue
	k = 0
	for i in a:
		if i % 4 == 1:
			k = 1
			break
		elif i % 4 == 3:
			if k != 0:
				k = min(k, check(i, 1))
			else:
				k = check(i, 1)
		elif k != 0:
			k = min(k, check2(i // 2, 1))
		else:
			k = check2(i // 2, 1)
	print(k)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	s = sum(l)
	ans = 0
	m = 10 ** 6
	if s % 2 == 0:
		print(ans)
	else:
		for i in range(n):
			ans = 0
			a = l[i]
			if l[i] % 2 == 0:
				while a % 2 == 0:
					ans = ans + 1
					a = a // 2
			else:
				while a % 2 != 0:
					ans = ans + 1
					a = a // 2
			if ans < m:
				m = ans
		print(m)


import math
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	if sum(l) % 2 == 0:
		print(0)
	else:
		e = [i for i in l if i % 2 == 0]
		o = [i for i in l if i % 2 != 0]
		c = 0
		d = 0
		while sum(o) % 2 != 0:
			d += 1
			for j in range(len(o)):
				o[j] = o[j] // 2
				if o[j] % 2 == 0:
					break
		if len(e) != 0:
			while sum(e) % 2 == 0:
				c += 1
				for j in range(len(e)):
					e[j] = e[j] // 2
					if e[j] % 2 != 0:
						break
		if c != 0:
			print(min(c, d))
		else:
			print(d)


for _ in range(int(input())):
	n = int(input())
	nums = list(map(int, input().split()))
	ans = float('inf')
	if sum(nums) % 2 != 0:
		for i in nums:
			count = 0
			if i % 2 == 0:
				while i % 2 == 0:
					i = i // 2
					count += 1
				ans = min(ans, count)
			else:
				while i % 2 != 0:
					i = i // 2
					count += 1
				ans = min(ans, count)
		print(ans)
	else:
		print(0)


t = int(input())
while t > 0:
	n = int(input())
	a = list(map(int, input().split()))
	even = []
	odd = []
	t_count_odd = 100000
	t_count_even = 100000
	for i in a:
		if i % 2 != 0:
			odd.append(i)
	for k in a:
		if k % 2 == 0:
			even.append(k)
	if len(odd) % 2 != 0:
		for y in odd:
			count_odd = 0
			while y % 2 != 0:
				y = y // 2
				count_odd = count_odd + 1
			t_count_odd = min(t_count_odd, count_odd)
		for z in even:
			count_even = 0
			while z % 2 == 0:
				z = z // 2
				count_even = count_even + 1
			t_count_even = min(t_count_even, count_even)
	if len(odd) % 2 == 0:
		print(0)
	else:
		print(min(t_count_even, t_count_odd))
	t = t - 1


def good(arr):
	s = sum(arr)
	if s % 2 == 0:
		return 0
	m = []
	for i in arr:
		c = 0
		while i // 2 % 2 == i % 2:
			i = i // 2
			c += 1
		c += 1
		m.append(c)
	return min(m)
for i in range(int(input())):
	input()
	arr = list(map(int, input().split()))
	print(good(arr))


def dfs(arr, n):
	mn = int(1000000000.0)
	for e in arr:
		k = e
		u = 1
		v = e % 2
		while v == k // 2 % 2 and k > 0:
			k //= 2
			u += 1
		if v != k // 2 % 2:
			mn = min(mn, u)
	return mn

def solve():
	n = int(input())
	arr = list(map(int, input().split()))
	if sum(arr) % 2 == 0:
		return 0
	return dfs(arr, n)
for i in range(int(input())):
	print(solve())


def ss(b, n):
	s = sum(b)
	if s % 2 == 0:
		return 0
	lst = []
	for i in range(n):
		x = a[i]
		count = 0
		while x > 0:
			if x % 2 == x // 2 % 2:
				count += 1
				x = x // 2
			else:
				lst.append(count + 1)
				break
		else:
			lst.append(count)
	return min(lst)
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	print(ss(a, n))


def summing(l):
	s = sum(l)
	if s % 2 == 0:
		return 0
	m = []
	for i in l:
		m.append(check(s - i, i))
	return min(m)

def check(s, i):
	cnt = 0
	while i > 0:
		cnt += 1
		i = i // 2
		if (s + i) % 2 == 0:
			return cnt
t = int(input())
for i in range(t):
	x = int(input())
	l = list(map(int, input().split()))
	print(summing(l))


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	oc = 0
	for ele in arr:
		if ele & 1:
			oc += 1
	if oc % 2 == 0:
		print(0)
	else:
		mn = float('inf')
		for ele in arr:
			if ele & 1:
				nc = 0
				while ele & 1:
					ele = ele // 2
					nc += 1
				mn = min(mn, nc)
			else:
				nc = 0
				while ele & 1 == 0:
					ele = ele // 2
					nc += 1
				mn = min(mn, nc)
		print(mn)


t = int(input(''))
for j in range(t):
	n = int(input(''))
	a = list(map(int, input('').split()))[:n]
	if sum(a) % 2 == 0:
		print(0)
	else:
		e = []
		o = []
		k = 0
		for z in range(n):
			if a[z] % 2 == 0:
				e.append(a[z])
			else:
				o.append(a[z])
		c = []
		for i in o:
			if (i - 1) % 4 == 0:
				c.append(1)
				k = 1
				break
			else:
				co = 0
				while i % 2 != 0:
					i = i // 2
					co += 1
				c.append(co)
		if k != 1:
			for i in e:
				if i % 4 != 0:
					c.append(1)
					break
				else:
					co = 0
					while i % 2 != 1:
						i = i // 2
						co += 1
					c.append(co)
		print(min(c))


inputt = int(input())
results = []
for i in range(inputt):
	ans = 500000000
	odd_stuff = []
	input()
	inp = input()
	arrayy = inp.split()
	arrayy = list(map(lambda x: int(x), arrayy))
	for it in arrayy:
		new_int = it
		n = 0
		if it % 2 == 0:
			while new_int % 2 == 0:
				n += 1
				new_int //= 2
		else:
			while new_int % 2 == 1:
				n += 1
				new_int //= 2
		ans = min(ans, n)
	if sum(arrayy) % 2 == 0:
		ans = 0
	results.append(ans)
for item in results:
	print(item)


for _ in range(int(input())):
	n = int(input())
	A = list(map(int, input().split()))
	odd_n = 0
	for i in range(n):
		if A[i] % 2 == 1:
			odd_n += 1
	if odd_n % 2 == 0:
		print(0)
	else:
		ans = 10 ** 18
		for i in range(n):
			a = A[i]
			res = 0
			if a % 2 == 1:
				while a % 2 == 1:
					a //= 2
					res += 1
			else:
				while a % 2 == 0:
					a //= 2
					res += 1
			ans = min(ans, res)
		print(ans)


import math
test = int(input())
resutl = []

def dfadfas(a):
	d = 0
	e = list(map(lambda i: [i, 0 if i % 2 else 1], a))
	while True:
		for i in range(len(a)):
			c = e[i][0]
			e[i][0] = int(c / 2)
			if e[i][0] % 2 == e[i][1]:
				d += 1
				return d
		d += 1
for i in range(test):
	input()
	s = 0
	a = list(map(int, input().split(' ')))
	for i in a:
		s += i
	if s % 2 == 0:
		resutl.append(0)
		continue
	resutl.append(dfadfas(a))
[print(i) for i in resutl]