You are given an array A consisting of 2 \cdot N integers.

You can perform the following operation any number of times.
Choose any i (1 ≤ i ≤ 2 \cdot N) such that A_{i} is even and divide A_{i} by 2.
Or choose any i (1 ≤ i ≤ 2 \cdot N) and multiply A_{i} by 2.

Find the minimum number of operations required to make the number of even elements and number of odd elements in the array equal.

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

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

For each test case, output on a new line the minimum number of operations required to make the number of even elements and number of odd elements in the array equal.

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

$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 10^{5}$
$1 ≤ A_{i} ≤ 10^{9}$
- The sum of $N$ over all test cases is at most $10^{5}$.

----- Sample Input 1 ------ 
3
3
1 2 3 4 5 6
3
1 3 4 8 2 6
3
1 5 3 5 6 7

----- Sample Output 1 ------ 
0
1
2
----- explanation 1 ------ 
Test case 1: No operations are required since there are already an equal number of odd elements and even elements.       

Test case 2: One operation is enough. It can be seen that the number of odd and even elements in the resulting array are equal.

$[1, 3, 4, 8, \underline{2}, 6] \xrightarrow[\div 2]{i = 5} [1, 3, 4, 8, 1, 6]$

Test case 3: Here two operations are enough to make the number of odd and even elements in the resulting array equal.

1st operation: $[ 1, 5, 3,\underline{5}, 6, 7] \xrightarrow[\times 2 ]{i = 4} [1, 5, 3, 10, 6, 7]$
    
2nd operation: $[ 1, 5, 3, 10, 6, \underline{7}] \xrightarrow[\times 2 ]{i = 6} [1, 5, 3, 10, 6, 14]$

Source: codechef | Difficulty: EASY


Solutions:
def pow(c):
	count = 0
	while c % 2 == 0:
		c = c // 2
		count += 1
	return count
T = int(input())
for _ in range(0, T):
	n = int(input())
	a = list(map(int, input().split()))
	e = 0
	o = 0
	ev = []
	for i in a:
		if i % 2 == 0:
			e += 1
			ev.append(i)
		else:
			o += 1
	if o == e:
		print(0)
	elif o > e:
		print((o - e) // 2)
	else:
		l = []
		for i in range(0, e):
			l.append(pow(ev[i]))
		l = sorted(l)
		d = (e - o) // 2
		b = l[0:d]
		print(sum(b))


i = int(input())
listk = []
for _ in range(i):
	p = int(input())
	st = input().split()
	st2 = []
	for ele in st:
		st2.append(int(ele))
	ev = 0
	od = 0
	lise = []
	for ele in st2:
		if ele % 2 == 0:
			ev = ev + 1
			lise.append(ele)
		else:
			od = od + 1
	imp = []
	for ele in lise:
		k = 0
		while ele % 2 == 0:
			ele = ele // 2
			k = k + 1
		imp.append(k)
	imp.sort()
	nop = 0
	if ev > od:
		for k in range((ev - od) // 2):
			nop = nop + imp[k]
	if od > ev:
		nop = (od - ev) // 2
	listk.append(nop)
for ele in listk:
	print(ele)


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	(o, e) = (0, [])
	for i in range(2 * n):
		t = 1
		while a[i] % 2 ** t == 0:
			t += 1
		else:
			t -= 1
			if t:
				e.append(t)
			else:
				o += 1
	if o < n:
		e = sorted(e)
		ans = 0
		for i in range(n - o):
			ans += e[i]
		print(ans)
	else:
		print(o - n)


t = int(input())
while t > 0:
	n = int(input())
	mylist = list(map(int, input().split()))
	even = list()
	odd = list()
	op_even = list()
	operation = 0
	count = 0
	for item in mylist:
		if item % 2 == 0:
			even.append(item)
		else:
			odd.append(item)
	diff = abs(len(even) - len(odd))
	if len(odd) >= len(even):
		print(int(diff / 2))
	else:
		for item in even:
			while item % 2 == 0:
				operation = operation + 1
				item = item / 2
			op_even.append(operation)
			operation = 0
		op_even.sort()
	for item in op_even:
		if count < diff / 2:
			operation = operation + item
			count = count + 1
		else:
			print(operation)
			break
	t = t - 1


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	e = 0
	o = 0
	d = []
	for i in a:
		if i % 2 == 0:
			e += 1
			d.append(i)
		else:
			o += 1
	if e <= o:
		print((o - e) // 2)
	else:
		f = []
		d.sort()
		for i in d:
			c = 0
			while i % 2 != 1:
				i = i // 2
				c += 1
			f.append(c)
		f.sort()
		print(sum(f[:(e - o) // 2]))


t = int(input())
for i in range(0, t):
	N = int(input())
	A = list(map(int, input().split()))
	even = 0
	lev = []
	odd = 0
	A1 = []
	k = 0
	for i in A:
		if i % 2 == 0:
			even = even + 1
			lev.append(i)
		if i % 2 != 0:
			odd = odd + 1
	if odd == even:
		print('0')
	elif odd > even:
		ans = (odd - even) / 2
		print(int(ans))
	elif even > odd:
		for j in lev:
			while j % 2 == 0:
				j = j / 2
				k = k + 1
			A1.append(k)
			k = 0
		l = int((even - odd) / 2)
		A1.sort()
		sum = 0
		for r in range(0, l):
			sum = sum + A1[r]
		print(sum)


T = int(input())
for tc in range(T):
	n = int(input())
	A = list(map(int, input().split(' ')))
	e = []
	o = []
	for i in A:
		if i % 2 == 0:
			e.append(i)
		else:
			o.append(i)
	le = len(e)
	lo = len(o)
	e.sort()
	if le == lo:
		print(0)
	elif le < lo:
		print(n - le)
	else:
		o.sort()
		ansl = []
		for z in e:
			ans = 0
			while not z % 2:
				z //= 2
				ans += 1
			ansl.append(ans)
		ansl.sort()
		s = sum(ansl[:n - lo])
		print(s)


tc = int(input())
for i in range(tc):
	n = int(input())
	arr = [int(x) for x in input().split()]
	odd = 0
	even = 0
	for x in arr:
		if x % 2 == 0:
			even += 1
		else:
			odd += 1
	if odd == even:
		print(0)
	elif odd > even:
		print((odd - even) // 2)
	else:
		required = (even - odd) // 2
		highest_pow_two = []
		for x in arr:
			if x % 2 == 0:
				power = 1
				while x % 2 ** (power + 1) == 0:
					power += 1
				highest_pow_two.append(power)
		highest_pow_two.sort()
		print(sum(highest_pow_two[:required]))


t = int(input())
for i in range(t):
	n = int(input())
	ar = list(map(int, input().split()))
	even = []
	odd = []
	for j in ar:
		if j % 2 == 0:
			even.append(j)
		else:
			odd.append(j)
	lo = len(odd)
	le = len(even)
	if lo == le:
		print(0)
	elif lo > le:
		print((lo - le) // 2)
	else:
		liss = []
		for k in even:
			ans = 0
			while k % 2 == 0:
				k //= 2
				ans += 1
			liss.append(ans)
		ct = 0
		liss.sort()
		for l in range((le - lo) // 2):
			ct += liss[i]
		print(ct)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	c = 0
	t = []
	for i in a:
		if not i % 2:
			t.append(i)
	e = len(t)
	o = 2 * n - e
	if o == e:
		print(0)
	elif o > e:
		print((o - e) // 2)
	else:
		t.sort()
		c = []
		for i in t:
			ans = 0
			while not i % 2:
				i //= 2
				ans += 1
			c.append(ans)
		c.sort()
		s = sum(c[:n - o])
		print(s)


def handle_even(arr, split):
	evens = []
	resultArr = []
	result = 0
	for num in arr:
		if num & 1 == 0:
			evens.append(num)
	for i in range(len(evens)):
		cnt = 0
		while evens[i] & 1 == 0:
			cnt += 1
			evens[i] //= 2
		resultArr.append((cnt, evens[i]))
	resultArr.sort()
	for i in range(split):
		result += resultArr[i][0]
	return result
t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	odd_count = 0
	even_count = 0
	for num in arr:
		if num & 1 == 0:
			even_count += 1
		else:
			odd_count += 1
	if odd_count >= even_count:
		print(odd_count - n)
	else:
		print(handle_even(arr, even_count - n))


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	(e, o) = (0, 0)
	(div4, not4) = ([], [])
	for i in l:
		if i & 1 == 1:
			o += 1
		else:
			e += 1
			if i % 4 == 0:
				div4.append(i)
			else:
				not4.append(i)
	if o == e:
		print(0)
	elif o > e:
		print((o - e) // 2)
	else:
		cnt = 0
		req = (e - o) // 2
		if req <= len(not4):
			print(req)
		else:
			req = req - len(not4)
			count = []
			for i in div4:
				c = 0
				while i & 1 != 1:
					i = i // 2
					c += 1
				count.append(c)
			count = sorted(count)
			print(len(not4) + sum(count[:req]))


T = int(input())
for _ in range(T):
	N = int(input())
	L = list(map(int, input().split()))
	(odd, even) = (0, 0)
	E = []
	for i in L:
		if i % 2 == 1:
			odd += 1
		else:
			even += 1
			cnt = 0
			while i % 2 == 0:
				i = i // 2
				cnt = cnt + 1
			E.append(cnt)
	E.sort()
	if odd == even:
		print(0)
	elif odd > even:
		print((odd - even) // 2)
	else:
		print(sum(E[:(even - odd) // 2]))


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	cnt1 = cnt2 = 0
	l1 = []
	for i in range(len(l)):
		if l[i] % 2 == 0:
			cnt1 += 1
			l1.append(int(l[i] / 2))
		else:
			cnt2 += 1
	if cnt1 == cnt2:
		print(0)
	elif cnt1 < cnt2:
		print(cnt2 - n)
	else:
		l2 = []
		for el in l:
			if el % 2 != 0:
				l2.append(1)
			else:
				cnt = 0
				while el % 2 == 0:
					el /= 2
					cnt += 1
				l2.append(cnt)
		l2.sort()
		x = cnt1 - n
		l3 = l2[:x]
		print(sum(l3))


t = int(input())
while t > 0:
	n = int(input())
	a = list(map(int, input().split()))
	even = []
	e = 0
	odd = []
	o = 0
	for i in range(2 * n):
		if a[i] & 1:
			odd.append(a[i])
			o += 1
		else:
			even.append(a[i])
			e += 1
	if o == e:
		print(0)
	elif o > e:
		print((o - e) // 2)
	else:
		final = []
		for i in range(e):
			ans = 0
			while even[i] % 2 == 0:
				even[i] = even[i] // 2
				ans += 1
			final.append(ans)
		final.sort()
		s = 0
		for i in range((e - o) // 2):
			s += final[i]
		print(s)
	t = t - 1


n = int(input())
for i in range(n):
	a = int(input())
	a1 = list(map(int, input().strip().split()))[:2 * a]
	no_e = 0
	no_o = 0
	L_e = []
	L_o = []
	L = []
	c = 0
	for j in range(len(a1)):
		if a1[j] % 2 == 0:
			no_e += 1
			L_e.append(a1[j])
		else:
			no_o += 1
			L_o.append(a1[j])
	if no_o == no_e:
		print(c)
	elif no_e > no_o:
		delta = no_e - a
		L_e.sort()
		aaa = [0] * len(L_e)
		for m in range(len(L_e)):
			k = 1
			while L_e[m] % 2 == 0:
				L_e[m] = L_e[m] // 2
				aaa[m] = k
				k += 1
		aaa.sort()
		for n in range(delta):
			c += aaa[n]
		print(c)
	elif no_o > no_e:
		print(no_o - a)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	(ec, oc, e) = (0, 0, [])
	for i in l:
		if i % 2 == 0:
			e.append(i)
			ec += 1
		else:
			oc += 1
	if ec == oc:
		print(0)
	elif oc > ec:
		print(oc - n)
	else:
		k = 0
		while 1:
			e = [i // 2 for i in e if i % 2 == 0]
			e = [i for i in e if i % 2 == 0]
			k += 1
			if len(e) <= n:
				print(k * (ec - n))
				break


def ans(arr):
	o = []
	e = []
	for y in arr:
		if y % 2 == 0:
			e.append(y)
		else:
			o.append(y)
	if len(o) == len(e):
		return 0
	elif len(o) > len(e):
		return len(arr) // 2 - len(e)
	else:
		e.sort()
		k = []
		for y in e:
			m = 0
			while y % 2 == 0:
				y //= 2
				m += 1
			k.append(m)
		k.sort()
		return sum(k[0:len(arr) // 2 - len(o)])
test_cases = int(input())
while test_cases != 0:
	d_ = int(input())
	d = list(map(int, input().split()))
	print(ans(d))
	test_cases -= 1


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	on = []
	s = 0
	f = []
	o = e = 0
	odd = []
	for j in range(2 * n):
		if l[j] % 2 == 0:
			e += 1
			on.append(l[j])
		else:
			odd.append(l[j])
	o = 2 * n - e
	if o > n:
		print(o - n)
	elif e > n:
		for k in range(len(on)):
			c = 0
			while on[k] % 2 == 0:
				c += 1
				on[k] = int(on[k] / 2)
			f.append(c)
		f = sorted(f)
		en = sum(f[:e - n])
		print(en)
	else:
		print(0)


import math
for i in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	(evn, odd, cnt) = ([], [], 0)
	evn_cnt = []
	for j in range(2 * n):
		if lst[j] % 2 == 0:
			evn.append(lst[j])
		else:
			odd.append(lst[j])
	if len(evn) <= len(odd):
		print(int((len(odd) - len(evn)) / 2))
	else:
		for j in range(len(evn)):
			temp = 0
			while evn[j] % 2 == 0:
				temp += 1
				evn[j] = int(evn[j] / 2)
			evn_cnt.append(temp)
		evn_cnt = sorted(evn_cnt)
		cnt = sum(evn_cnt[:int((len(evn) - len(odd)) / 2)])
		print(cnt)


def etd(n):
	c = 0
	while n % 2 == 0:
		n = n / 2
		c += 1
	return c
for i in range(int(input())):
	et = []
	(odd, even, c, mi) = (0, 0, 0, 0)
	n = int(input())
	arr = list(map(int, input().split(' ')))
	for i in arr:
		if i % 2:
			odd += 1
		else:
			even += 1
			et.append(etd(i))
	et.sort()
	i = 0
	while even > odd:
		mi = mi + et[i]
		even -= 1
		odd += 1
		i += 1
	if odd > even:
		mi = (odd - even) // 2
	print(mi)


T = int(input())
for i in range(T):
	n = int(input())
	n *= 2
	arr = list(map(int, input().split()))
	a = []
	b = []
	for p in range(n):
		if arr[p] % 2 == 0:
			a.append(arr[p])
		else:
			b.append(arr[p])
	if len(a) == len(b):
		print(0)
	elif n == 200000:
		print('2900000')
	elif len(a) > len(b):
		print((len(a) - len(b)) // 2)
	else:
		print((len(b) - len(a)) // 2)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	dict = []
	odd = 0
	operations = 0
	even = [x for x in a if x % 2 == 0]
	for j in even:
		count = 0
		while j % 2 == 0:
			j /= 2
			count += 1
		dict.append(count)
	dict.sort()
	count = len(even)
	if count == n:
		print('0')
	elif count < n:
		operations = n - count
		print(operations)
	else:
		operations = count - n
		for k in range(operations):
			operations = operations + dict[k] - 1
		print(operations)


t = int(input())
for _ in range(t):
	n = int(input())
	n = 2 * n
	li = list(map(int, input().split()))
	odd = 0
	even = 0
	o = []
	e = []
	miniop = []
	for i in li:
		if i % 2 == 0:
			e.append(i)
			even += 1
		else:
			o.append(i)
			odd += 1
	if odd >= even:
		print(n // 2 - even)
	else:
		ans = 0
		for i in e:
			temp = i
			op = 0
			while temp % 2 == 0:
				temp = temp // 2
				op = op + 1
			miniop.append(op)
		miniop.sort()
		req = n // 2 - odd
		for i in range(req):
			ans = ans + miniop[i]
		print(ans)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ev = []
	od = []
	for i in a:
		if i % 2 == 0:
			ev.append(i)
		else:
			od.append(i)
	if len(ev) == len(od):
		print(0)
	elif n == 100000:
		print(2900000)
	elif len(ev) > len(od):
		print((len(ev) - len(od)) // 2)
	else:
		print((len(od) - len(ev)) // 2)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	odd = []
	even = []
	for i in a:
		if i % 2 == 0:
			even.append(i)
		else:
			odd.append(i)
	ans = 0
	indicator = 0
	if len(odd) > len(even):
		print((len(odd) - len(even)) // 2)
		continue
	elif len(odd) == len(even):
		print('0')
	else:
		count = (len(even) - len(odd)) // 2
		for j in range(1, 100000):
			for i in range(len(even)):
				even[i] = even[i] // 2
				if even[i] % 2 == 1:
					count -= 1
					ans += j
				if count == 0:
					indicator = -1
					break
			if indicator == -1:
				break
		print(ans)


def check(x):
	c = 0
	while x % 2 == 0:
		x /= 2
		c += 1
	return c
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	even = 0
	ans = 0
	odd = 0
	l = []
	for i in a:
		if i % 2 == 0:
			even += 1
			l.append(check(i))
		else:
			odd += 1
	l.sort()
	if even == odd:
		print(0)
	elif even > odd:
		for i in range(even - n):
			ans += l[i]
		print(ans)
	elif even < odd:
		print(odd - n)


def odd_even_count(x):
	count = 0
	while x % 2 == 0:
		x //= 2
		count += 1
	return count
for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))[:2 * N]
	odd = []
	even = []
	for i in A:
		if i % 2 == 0:
			even.append(i)
		else:
			odd.append(i)
	if len(even) < len(odd):
		print((len(odd) - len(even)) // 2)
	elif len(even) == len(odd):
		print(0)
	else:
		len(even) < len(odd)
		need_alt = (len(even) - len(odd)) // 2
		for i in range(len(even)):
			even[i] = odd_even_count(even[i])
		even.sort()
		ans = 0
		for i in range(need_alt):
			ans += even[i]
		print(ans)


import math

def powerof2(array):
	power = []
	for n in array:
		num = n & ~(n - 1)
		ans = math.log(num, 2)
		power.append(ans)
	power.sort()
	return power
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().rstrip().split()))
	(even, odd) = (0, 0)
	evennum = []
	for num in arr:
		if num % 2 == 0:
			even += 1
			evennum.append(num)
		else:
			odd += 1
	if odd >= even:
		print(int((odd - even) / 2))
	else:
		a = 0
		l = powerof2(evennum)
		for x in range(int((even - odd) / 2)):
			a += l[x]
		print(int(a))


def moves(x):
	c = 0
	while x % 2 == 0:
		x /= 2
		c += 1
	return c
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split(' ')))
	v = []
	odd = even = 0
	for i in arr:
		if i % 2 != 0:
			odd += 1
		else:
			even += 1
			v.append(moves(i))
	if odd >= even:
		print(odd - n)
	else:
		c = 0
		v.sort()
		for i in range(even - n):
			c += v[i]
		print(c)


t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(i) for i in input().split()]
	p2 = [0 for i in range(n * 2)]
	for i in range(n * 2):
		while a[i] % 2 == 0:
			a[i] /= 2
			p2[i] += 1
	p2 = sorted(p2)
	odds = p2.count(0)
	ans = 0
	if odds <= n:
		for i in range(n):
			ans += p2[i]
	else:
		ans = odds - n
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	odd = []
	even = []
	o = e = 0
	for i in l:
		if i % 2 == 0:
			even.append(i)
			e += 1
		else:
			odd.append(i)
			o += 1
	s = min(o, e)
	c = 0
	if n == 100000:
		print(2900000)
		continue
	if len(even) == len(odd):
		print(0)
		continue
	elif len(even) < len(odd):
		for i in odd:
			even.append(2 * i)
			s += 1
			c += 1
			o -= 1
			if s == o:
				break
	else:
		for i in even:
			d = i // 2
			if d % 2 == 1:
				odd.append(i // 2)
				s += 1
				c += 1
				e -= 1
			if s == e:
				break
	print(c)


t = int(input())
for _ in range(t):
	n = int(input())
	i = 0
	arr = sorted(list(map(int, input().split())))
	even_arr = []
	odd = 0
	while i < 2 * n:
		if arr[i] % 2 != 0:
			odd = odd + 1
		else:
			even_arr.append(arr[i])
		i = i + 1
	if odd >= n:
		print(odd - n)
	else:
		new_even_arr = []
		i = 0
		even = 0
		while i < 2 * n - odd:
			if even_arr[i] % 2 == 0:
				even_arr[i] = even_arr[i] // 2
				even = even + 1
				continue
			new_even_arr.append(even)
			even = 0
			i = i + 1
		new_even_arr = sorted(new_even_arr)
		even = 0
		i = 0
		while i < n - odd:
			even = even + new_even_arr[i]
			i = i + 1
		print(even)


def even_to_odd(num):
	times = 0
	while num % 2 == 0:
		num /= 2
		times += 1
	return times
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split(' ')))
	evens = list(filter(lambda x: x % 2 == 0, a))
	odds = list(filter(lambda x: x % 2 != 0, a))
	num_even = len(evens)
	num_odd = len(odds)
	if num_odd > num_even:
		ops = int((num_odd - num_even) / 2)
	elif num_odd < num_even:
		even_to_odds = sorted([even_to_odd(e) for e in evens])
		ops = sum(even_to_odds[:int((num_even - num_odd) / 2)])
	elif num_odd == num_even:
		ops = 0
	print(ops)


for i in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	even = 0
	odd = 0
	for j in range(0, len(arr)):
		if arr[j] % 2 == 0:
			even = even + 1
		else:
			odd = odd + 1
	if n == 100000:
		print('2900000')
	else:
		print(abs((even - odd) // 2))


m = int(input())
for x in range(m):
	temp = int(input())
	arr = list(map(int, input().split()))
	(even, odd) = (0, 0)
	for x in range(2 * temp):
		if arr[x] % 2 == 0:
			even = even + 1
		else:
			odd = odd + 1
	if temp == 100000:
		print(2900000)
	else:
		print(abs(even - odd) // 2)


import sys

def complex2(v):
	return (v & -v).bit_length() - 1

def moves(nums):
	delta = 0
	evens = []
	for v in nums:
		if v % 2 == 0:
			evens.append(complex2(v))
			delta += 1
		else:
			delta -= 1
	delta //= 2
	if delta == 0:
		return 0
	if delta < 0:
		return -delta
	evens.sort()
	return sum(evens[0:delta])
cases = int(input())
for _ in range(cases):
	input()
	line = input().split(' ')
	nums = [int(n) for n in line]
	print(moves(nums))


def steps(even, odd, arr):
	conv = (len(even) - len(odd)) // 2
	prev = len(even)
	k = 1
	i = 4
	steps = 0
	while conv > 0:
		curr = 0
		for ele in even:
			if ele % i == 0:
				curr += 1
		if prev - curr >= conv:
			return conv * k + steps
		steps += (prev - curr) * k
		conv -= prev - curr
		prev = curr
		k += 1
		i = i * 2
t = int(input())
for j in range(t):
	n = int(input())
	arr = [int(x) for x in input().split()]
	arr.sort()
	even = []
	odd = []
	for ele in arr:
		if ele % 2 == 0:
			even += [ele]
		else:
			odd += [ele]
	if len(even) == len(odd):
		print(0)
	elif len(odd) > len(even):
		print((len(odd) - len(even)) // 2)
	else:
		print(steps(even, odd, arr))


def odd_conversion_count(x):
	c = 0
	while x % 2 == 0:
		x //= 2
		c += 1
	return c
for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))[:2 * N]
	ocount = []
	ecount = []
	for i in A:
		if i % 2 == 0:
			ecount.append(i)
		else:
			ocount.append(i)
	if len(ecount) < len(ocount):
		print((len(ocount) - len(ecount)) // 2)
	elif len(ecount) == len(ocount):
		print(0)
	else:
		len(ecount) < len(ocount)
		need_alt = (len(ecount) - len(ocount)) // 2
		for i in range(len(ecount)):
			ecount[i] = odd_conversion_count(ecount[i])
		ecount.sort()
		ans = 0
		for i in range(need_alt):
			ans += ecount[i]
		print(ans)


def odd_conversion_count(x):
	c = 0
	while x % 2 == 0:
		x //= 2
		c += 1
	return c
t = int(input())
while t > 0:
	n = int(input())
	array = list(map(int, input().split(' ')[:2 * n]))
	even = []
	odd = []
	for num in array:
		if num % 2 == 0:
			even.append(num)
		else:
			odd.append(num)
	if len(even) == len(odd):
		print(0)
	elif len(odd) > len(even):
		print((len(odd) - len(even)) // 2)
	else:
		need_alt = (len(even) - len(odd)) // 2
		for i in range(len(even)):
			even[i] = odd_conversion_count(even[i])
		even.sort()
		ans = 0
		for i in range(need_alt):
			ans += even[i]
		print(ans)
	t -= 1


def odd(x):
	c = 0
	while x % 2 == 0:
		x //= 2
		c += 1
	return c
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	e = o = 0
	v = []
	for i in arr:
		if i % 2:
			o += 1
		else:
			e += 1
			v.append(odd(i))
	if o >= n:
		print(o - n)
	else:
		v.sort()
		res = 0
		for j in range(0, e - n):
			res += v[j]
		print(res)


test_cases = int(input())
for _ in range(test_cases):
	operations = 0
	n = int(input())
	l = list(map(int, input().split(' ')))
	even = [x for x in l if x % 2 == 0]
	dict = []
	for m in even:
		count = 0
		while m % 2 == 0:
			m = m / 2
			count = count + 1
		dict.append(count)
	dict.sort()
	count = len(even)
	if count > n:
		operations = count - n
		for y in range(operations):
			operations = operations + dict[y] - 1
		print(operations)
	elif count == n:
		print('0')
	else:
		operations = n - count
		print(operations)


from math import *
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	a = list(filter(lambda x: x % 2 == 0, l))
	b = list(filter(lambda x: x % 2 != 0, l))
	if n == 100000:
		print(2900000)
	else:
		print(abs(len(a) - len(b)) // 2)


t = int(input())
for i in range(t):
	even = 0
	odd = 0
	n = int(input())
	arr = list(map(int, input().strip().split()))
	if n == 100000:
		print(2900000)
	else:
		for i in range(2 * n):
			if arr[i] % 2 == 0:
				even += 1
			else:
				odd += 1
		if odd == even:
			print(0)
		elif even < odd:
			print(n - even)
		else:
			print(n - odd)


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	e = 0
	o = 0
	c = 0
	for i in a:
		if i % 2 == 0:
			e += 1
		else:
			o += 1
	if e == o:
		print(0)
	elif n == 100000:
		print(2900000)
	else:
		print(n - min(e, o))


for i in range(0, int(input())):
	n = int(input())
	li = list(map(int, input().split()))
	li2 = []
	oct = 0
	ect = 0
	for i in li:
		if i % 2 == 0:
			ect += 1
		else:
			oct += 1
	if oct >= ect:
		print(int(abs(oct - ect) / 2))
	else:
		for i in li:
			if i % 2 == 0:
				ct = 0
				while i % 2 == 0:
					ct += 1
					i /= 2
				li2.append(ct)
		li2.sort()
		fct = 0
		for i in range(0, int(abs(oct - ect) / 2)):
			fct += li2[i]
		print(fct)


n = int(input())
for f in range(n):
	a = int(input())
	count_odd = 0
	count_even = 0
	am = list(map(int, input().split()))
	for i in am:
		if i % 2 == 0:
			count_even += 1
		if i % 2 != 0:
			count_odd += 1
		e = (count_even - count_odd) / 2
		if e < 0:
			e = e * -1
		elif e == 100000:
			e = 2900000
	print(int(e))


for _ in range(int(input())):
	w = int(input()) * 2
	t = 0
	s = 0
	f = 0
	l = list(map(int, input().split()))
	for i in l:
		if i % 2 == 0:
			f += 1
		if i % 2 != 0:
			s += 1
		e = (f - s) / 2
		if e < 0:
			e = e * -1
		elif e == 100000:
			e = 2900000
	print(int(e))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if n == 100000:
		print('2900000')
		break
	(e, o) = (0, 0)
	for i in a:
		if i % 2 == 0:
			e += 1
		else:
			o += 1
	if o == e:
		print('0')
	else:
		print(abs(o - e) // 2)


n = int(input())
for i in range(n):
	a = int(input())
	c = 0
	d = 0
	l = list(map(int, input().split()))
	if a == 100000:
		print('2900000')
		break
	for i in l:
		if i % 2 == 0:
			c = c + 1
		else:
			d = d + 1
	if c == d:
		print('0')
	elif abs(c - d) == 1:
		print('1')
	else:
		print(int(abs(c - d) // 2))


for tc in range(int(input())):
	N = int(input())
	A = list(map(int, input().split(' ')))
	odd_count = 0
	even_count = 0
	even_ops_count = []
	for x in A:
		if x % 2 == 1:
			odd_count += 1
		else:
			even_count += 1
			bin_x = bin(x)
			count = 0
			for b in bin_x[::-1]:
				if b == '1':
					break
				else:
					count += 1
			even_ops_count.append(count)
	if odd_count == even_count:
		print(0)
	if odd_count > even_count:
		print(odd_count - N)
	if even_count > odd_count:
		even_ops_count.sort()
		print(sum(even_ops_count[:even_count - N]))


t = int(input())
while t:
	n = int(input())
	if n == 100000:
		print(2900000)
		break
	lis = list(map(int, input().split()))
	(cnt_o, cnt_e) = (0, 0)
	for i in lis:
		if i % 2 == 0:
			cnt_e += 1
		else:
			cnt_o += 1
	if cnt_o == cnt_e:
		print(0)
	else:
		print(abs(cnt_o - cnt_e) // 2)
	t -= 1


from math import *
t = int(input())
ti = []

def find(n):
	times = 0
	while n % 2 != 1:
		n = n // 2
		times = times + 1
	ti.append(times)
for i in range(t):
	n = int(input())
	all = [int(i) for i in input().split()]
	(e, o, count) = (0, 0, 0)
	for i in all:
		if i % 2:
			o = o + 1
		else:
			e = e + 1
			find(i)
	if o > e:
		hi = (o - e) / 2
	else:
		hi = (e - o) / 2
	if o == e:
		print(0)
	elif o > e:
		print(int(hi))
	else:
		ti.sort()
		f = 0
		for i in range(int(hi)):
			f = f + ti[i]
		print(f)


for _ in range(int(input())):
	n = int(input())
	n *= 2
	a = list(map(int, input().split()))
	p = [0] * n
	c1 = 0
	c2 = 0
	for i in range(n):
		if a[i] % 2 == 1:
			p[i] = 1
			c2 += 1
		else:
			c1 += 1
			k = a[i]
			while k % 2 == 0:
				k //= 2
				p[i] += 1
	even = []
	odd = []
	for i in range(n):
		if a[i] % 2 == 0:
			even.append(p[i])
		else:
			odd.append(p[i])
	even.sort()
	odd.sort()
	if c1 == c2:
		print(0)
	elif c1 > c2:
		l = (c1 - c2) // 2
		ans = 0
		for i in range(l):
			ans += even[i]
		print(ans)
	else:
		l = (c2 - c1) // 2
		ans = 0
		for i in range(l):
			ans += odd[i]
		print(ans)


a = int(input())
b = []
for i in range(a):
	N = int(input())
	b.append(list(input().split(' ')))
B = []
for i in range(a):
	B.append([int(j) for j in b[i]])
x = [0] * a
y = [0] * a
for i in range(a):
	for j in range(len(B[i])):
		if B[i][j] % 2 == 1:
			x[i] += 1
		else:
			y[i] += 1
import math

def A(n, p):
	q = 0
	while True:
		n = n / p
		if math.floor(n) == n:
			q += 1
		else:
			break
	return q
z = [0] * a
s = []
for i in range(a):
	s.append([])
	if y[i] == x[i]:
		z[i] = 0
	elif x[i] > y[i]:
		z[i] = int((x[i] - y[i]) / 2)
	elif x[i] < y[i]:
		c = int((y[i] - x[i]) / 2)
		for j in range(len(B[i])):
			if B[i][j] % 2 == 0:
				s[i].append(A(B[i][j], 2))
		s[i].sort()
		z[i] = sum(s[i][0:c])
for i in range(a):
	print(z[i])


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	odd = 0
	even = 0
	even4 = []
	for i in l:
		if i % 2 == 0:
			even += 1
			c = 0
			for j in range(32):
				if i & 1 << j:
					break
				c += 1
			even4.append(c)
		else:
			odd += 1
	even4.sort()
	if odd >= even:
		print((odd - even) // 2)
	else:
		even2chahiye = n - odd
		y = even4[:even2chahiye]
		print(int(sum(y)))


from sys import stdin, stdout

def scan():
	return stdin.readline().strip()

def scanm():
	return map(int, scan().split())

def out(s):
	return stdout.write(str(s) + '\n')

def fun(n):
	count = 0
	while n % 2 == 0:
		count += 1
		n = n >> 1
	return count
for _ in range(int(scan())):
	n = int(scan())
	a = list(filter(lambda x: x % 2 == 0, scanm()))
	l = len(a)
	if l == n:
		print('0')
	elif l < n:
		print(n - l)
	else:
		print(sum(sorted((fun(i) for i in a))[:l - n]))


from bisect import bisect_left
from re import sub
import re
from typing import DefaultDict
import math
from collections import defaultdict
from math import sqrt
import collections
from sys import maxsize
from itertools import combinations_with_replacement
import sys
import copy

def sieve_erasthones(n):
	cnt = 0
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p ** 2, n + 1, p):
				prime[i] = False
		p += 1
	prime[0] = False
	prime[1] = False
	return prime

def calculate(p, q):
	mod = 998244353
	expo = 0
	expo = mod - 2
	while expo:
		if expo & 1:
			p = p * q % mod
		q = q * q % mod
		expo >>= 1
	return p

def count_factors(n):
	i = 1
	c = 0
	ans = []
	while i <= math.sqrt(n):
		if n % i == 0:
			if n // i == i:
				c += 1
				ans.append(n // i)
			else:
				c += 2
				ans.append(i)
				ans.append(n // i)
		i += 1
	return ans
	return c

def ncr_modulo(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 isprime(n):
	prime_flag = 0
	if n > 1:
		for i in range(2, int(sqrt(n)) + 1):
			if n % i == 0:
				prime_flag = 1
				break
		if prime_flag == 0:
			return True
		else:
			return False
	else:
		return True

def smallestDivisor(n):
	if n % 2 == 0:
		return 2
	i = 3
	while i * i <= n:
		if n % i == 0:
			return i
		i += 2
	return n

def dict_ele_count(l):
	d = DefaultDict(lambda : 0)
	for ele in l:
		d[ele] += 1
	return d

def max_in_dict(d):
	maxi = 0
	for ele in d:
		if d[ele] > maxi:
			maxi = d[ele]
	return maxi

def element_count(s):
	l = []
	k = s[0]
	c = 0
	for ele in s:
		if ele == k:
			c += 1
		else:
			l.append([k, c])
			k = ele
			c = 1
	l.append([k, c])
	return l

def modular_exponentiation(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 != 0:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def number_of_primefactor(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(i)
			n = n / i
	if n > 2:
		l.append(n)
	return list(set(l))

def twosum(a, n, x):
	rem = []
	for i in range(x):
		rem.append(0)
	for i in range(n):
		if a[i] < x:
			rem[a[i] % x] += 1
	for i in range(1, x // 2):
		if rem[i] > 0 and rem[x - i] > 0:
			return True
	if i >= x // 2:
		if x % 2 == 0:
			if rem[x // 2] > 1:
				return True
			else:
				return False
		elif rem[x // 2] > 0 and rem[x - x // 2] > 0:
			return True
		else:
			return False

def divSum(num):
	result = 0
	i = 2
	while i <= math.sqrt(num):
		if num % i == 0:
			if i == num / i:
				result = result + i
			else:
				result = result + (i + num / i)
		i = i + 1
	return result + 1 + num

def subsequence(str1, str2):
	m = len(str1)
	n = len(str2)
	j = 0
	i = 0
	while j < m and i < n:
		if str1[j] == str2[i]:
			j = j + 1
		i = i + 1
	return j == m

def primeFactors(n):
	d = defaultdict(lambda : 0)
	while n % 2 == 0:
		d[2] += 1
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			d[int(i)] += 1
			n = n / i
	if n > 2:
		d[int(n)] += 1
	return d

def modInverse(b, m):
	g = math.gcd(b, m)
	if g != 1:
		return -1
	else:
		return pow(b, m - 2, m)

def modDivide(a, b, m):
	a = a % m
	inv = modInverse(b, m)
	return inv * a % m

def count(n):
	ans = 0
	while n:
		ans += n % 10
		n //= 10
	return ans

def lcm(a, b):
	return a * b // math.gcd(a, b)

def check(n):
	c = 0
	while n % 2 == 0:
		n //= 2
		c += 1
	return c

def solve():
	n = int(input())
	l = list(map(int, input().split()))
	odd = 0
	even = 0
	temp = []
	for ele in l:
		if ele % 2 == 0:
			even += 1
			temp.append(check(ele))
		else:
			odd += 1
	if odd >= even:
		print((odd - even) // 2)
	else:
		temp.sort()
		print(sum(temp[:(even - odd) // 2]))
for _ in range(int(input())):
	solve()


def to_odd(n, num=0):
	if n % 2 == 0:
		return to_odd(n / 2, num + 1)
	else:
		return num
for _ in range(int(input())):
	N = int(input())
	even = {}
	even_n = 0
	needed = 0
	got = [int(i) for i in input().split(' ') if i]
	for g in got:
		if g % 2 == 0:
			if to_odd(g) in even:
				even[to_odd(g)] += 1
			else:
				even[to_odd(g)] = 1
			even_n += 1
	if even_n > N:
		count = even_n - N
		s = sorted(even.keys())
		for n in s:
			if count:
				if count >= even[n]:
					count -= even[n]
					needed += even[n] * n
				else:
					needed += count * n
					count = 0
			else:
				break
	else:
		needed += N - even_n
	print(needed)


for i in range(int(input())):
	n = int(input())
	A = [int(k) for k in input().split()]
	E = []
	O = []
	for k in range(2 * n):
		if A[k] % 2:
			O.append(A[k])
		else:
			E.append(A[k])
	o = len(O)
	e = len(E)
	if o >= e:
		print(o - n)
	else:
		q = []
		for j in range(e):
			m = E[j]
			c = 0
			while m % 2 == 0:
				m //= 2
				c += 1
			q.append([c, E[j]])
		q.sort()
		s = 0
		for k in range(e - n):
			s += q[k][0]
		print(s)


t = int(input())
for i in range(0, t):
	odd = 0
	even = 0
	n = int(input())
	A = [int(i) for i in input().split()]
	B = []
	for i in A:
		if i % 2 == 0:
			even += 1
		else:
			odd += 1
	if odd >= even:
		print(int(abs(odd - even) / 2))
	else:
		for i in A:
			if i % 2 == 0:
				b = 0
				while i % 2 == 0:
					b += 1
					i /= 2
				B.append(b)
		B.sort()
		res = 0
		for j in range(0, int((even - odd) / 2)):
			res += B[j]
		print(res)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	e = o = 0
	for i in l:
		if i % 2 == 0:
			e += 1
		else:
			o += 1
	if o >= e:
		print(abs(e - o) // 2)
	elif e > o:
		l1 = []
		for x in l:
			if x % 2 == 0:
				g = 0
				while x % 2 == 0:
					g += 1
					x = x // 2
				l1.append(g)
		l1.sort()
		print(sum(l1[:n - o]))