She is skilled in all kinds of magics, and is keen on inventing new one.

—Perfect Memento in Strict Sense

Patchouli is making a magical talisman. She initially has $n$ magical tokens. Their magical power can be represented with positive integers $a_1, a_2, \ldots, a_n$.

Patchouli may perform the following two operations on the tokens.

Fusion: Patchouli chooses two tokens, removes them, and creates a new token with magical power equal to the sum of the two chosen tokens.

Reduction: Patchouli chooses a token with an even value of magical power $x$, removes it and creates a new token with magical power equal to $\frac{x}{2}$.

Tokens are more effective when their magical powers are odd values. Please help Patchouli to find the minimum number of operations she needs to make magical powers of all tokens odd values.


-----Input-----

Each test contains multiple test cases.

The first line contains a single integer $t$ ($1 \leq t \leq 10^3$) — the number of test cases. The description of the test cases follows.

For each test case, the first line contains one integer $n$ ($1 \leq n\leq 2\cdot 10^5$) — the initial number of tokens.

The second line contains $n$ intergers $a_1,a_2,\ldots,a_n$ ($1 \leq a_i \leq 10^9$) — the initial magical power of the $n$ tokens.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.


-----Output-----

For each test case, print a single integer — the minimum number of operations Patchouli needs to make all tokens have an odd value of magical power.

It can be shown that under such restrictions the required sequence of operations exists.


-----Examples-----

Input
4
2
1 9
3
1 1 2
3
2 4 8
3
1049600 33792 1280
Output
0
1
3
10


-----Note-----

Test case 1:

$a$ consists solely of odd numbers initially.

Test case 2:

Choose the tokens with magical power of $1$ and $2$ and perform Fusion. Now $a=[1,3]$, both are odd numbers.

Test case 3:

Choose the tokens with magical power of $2$ and $8$ and perform Fusion. Now $a=[4,10]$.

Choose the token with magical power of $10$ and perform Reduction. Now $a=[4,5]$.

Choose the tokens with magical power of $4$ and $5$ and perform Fusion. Now $a=[9]$, and $9$ is an odd number.

It can be shown that you can not make all the magical powers odd numbers in less than $3$ moves, so the answer is $3$.

Source: codeforces | Difficulty: EASY
Tags: Bit manipulation

Constructive algorithms

Sorting

Greedy algorithms


Solutions:
for s in [*open(0)][2::2]:
	a = [x & -x for x in map(int, s.split())]
	m = a.count((b := min(a)))
	(x, y, z) = (bin(x)[::-1].find('1') for x in (b, b * m, b * m - m))
	print(len(a) - m + min(m * x, m - 1 + y, m - 2 + x + 1) * (b > 1))


for s in [*open(0)][2::2]:
	b = min((a := [x & -x for x in map(int, s.split())]))
	print(len(a) + min((k := (bin(b)[::-1].find('1') - 1)), k * a.count(b)))


for i in range(int(input())):
	n = int(input())
	lst = [int(x) for x in input().split()]
	flag = False
	x = 0
	count = 0
	for element in lst:
		if element & 1:
			flag = True
		else:
			x |= element
			count += 1
	if flag:
		print(count)
	else:
		x = x & ~x + 1
		count = 0
		while x > 1:
			count += 1
			x >>= 1
		print(n - 1 + count)


t = int(input())
g = 1
d = []
while g < 10 ** 9:
	d.append(g)
	g *= 2
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	nechot = 0
	mina = 0
	for i in range(n):
		if a[i] & 1 == 1:
			nechot += 1
		if nechot == 0:
			j = 0
			mina |= a[i]
	if nechot == 0:
		j = 0
		while mina & d[j] == 0:
			j += 1
		print(j + n - 1)
	else:
		print(n - nechot)


import math

class MagicalTalisman:

	def operate(self, n, a):
		odd = 0
		even = 0
		minPower = a[0] & -a[0]
		for i in a:
			if i % 2:
				odd += 1
			else:
				even += 1
				minPower = min(minPower, i & -i)
		if odd > 0:
			print(even)
		else:
			print(int(math.log(minPower, 2)) + even - 1)
		return
T = int(input())
while T:
	T -= 1
	n = int(input())
	a = list(map(int, input().split()))
	MagicalTalisman().operate(n, a)


tc = int(input())
for t in range(tc):
	n = int(input())
	arr = list(map(int, input().split()))
	num = 0
	coun = n - 1
	odd = 0
	for j in range(n):
		num = num | arr[j]
		if arr[j] % 2 == 1:
			odd += 1
	if odd:
		coun = n - odd
	while num % 2 != 1:
		num = num >> 1
		coun += 1
	print(coun)


import math
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	od = 0
	x = a[0]
	for i in a:
		if i & 1:
			od += 1
		x = math.gcd(x, i)
	if od > 0:
		print(n - od)
		continue
	c = 0
	while x & 1 != 1:
		x = x >> 1
		c += 1
	print(c + n - 1)


import math
for _ in range(int(input())):
	n = int(input())
	li = list(map(int, input().split()))
	li2 = list()
	gcd = li[0]
	for i in li:
		if i % 2 == 0:
			li2.append(i)
		gcd = math.gcd(gcd, i)
	cnt = 0
	sm = sum(li2)
	if len(li2) == 0:
		print(0)
	elif len(li2) == n:
		while gcd % 2 == 0:
			gcd = gcd // 2
			cnt += 1
		print(cnt + n - 1)
	else:
		print(len(li2))


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

def solve():
	n = int(input())
	arr = [int(i) for i in input().split()]
	e = [ctz(i) for i in arr if i % 2 == 0]
	o = n - len(e)
	if o:
		return len(e)
	return min(e) + len(e) - 1

def main():
	for _ in range(int(input())):
		print(solve())
	return
main()


for t in range(int(input())):
	n = int(input())
	s = list(map(int, input().split()))
	f = False
	k = 0
	for i in range(0, n):
		if s[i] % 2 == 1:
			f = True
		else:
			k += 1
	if f:
		print(k)
	else:
		y = s[0]
		for i in range(1, n):
			y = y | s[i]
		min = 0
		while y % 2 == 0:
			y //= 2
			min += 1
		print(min + len(s) - 1)


t = int(input())
for _ in range(t):
	input()
	a = [int(i) for i in input().split()]
	m = sum((1 for i in a if i & 1 == 0))
	if m > 0:
		x = min((i for i in a if i & 1 == 1), default=None)
		if not x:

			def first_set_bit(n):
				return n - (n & n - 1)
			x = min(a, key=first_set_bit)
			m -= 1
			while x & 1 == 0:
				x >>= 1
				m += 1
	print(m)


import math

def solve():
	n = int(input())
	l = list(map(int, input().split()))
	odds = 0
	evens = 0
	min = 10 ** 9
	for i in l:
		if i % 2 == 0:
			bit = int(math.log2(i & -i))
			if bit < min:
				min = bit
			evens += 1
		else:
			odds += 1
	if odds > 0:
		print(evens)
	else:
		print(min + n - 1)
t = int(input())
while t > 0:
	solve()
	t -= 1


import math

def work(a):
	mink = 1000000000.0 + 1
	(c, b) = (0, 0)
	for o in a:
		if o & 1:
			c += 1
		else:
			b += 1
			mink = min(mink, math.log2(o & -o))
	if c != 0:
		print(b)
	else:
		print(int(mink + b - 1))
n = int(input())
while n:
	n -= 1
	input()
	a = list(map(int, input().split()))
	work(a)


import math

def solve():
	x = int(input())
	arr = input().split()
	for i in range(len(arr)):
		arr[i] = int(arr[i])
	odd = 0
	even = 0
	reduction = 9999999999
	for i in range(len(arr)):
		if arr[i] % 2 == 0:
			even += 1
			temp = arr[i]
			cc = temp & ~(temp - 1)
			if reduction > cc:
				reduction = cc
		else:
			odd += 1
	if odd > 0:
		print(even)
	else:
		print(int(even - 1 + math.log2(reduction)))
t = int(input())
for i in range(t):
	solve()


for _ in ' ' * int(input()):
	n = int(input())
	a = list(map(int, input().split()))
	op = any((i & 1 for i in a))
	ec = sum((1 - (i & 1) for i in a))
	if not ec:
		print(0)
	elif op:
		print(ec)
	else:
		print(ec - 2 + min([len(bin(x & -x)[2:]) for x in a]))


from math import log2
import sys
for t in range(int(input())):
	n = int(input())
	arr = [int(i) for i in input().split()]
	mindist = sys.maxsize
	evens = 0
	odds = 0
	for i in arr:
		if not i & 1:
			evens += 1
			dist = i & ~(i - 1)
			if dist < mindist:
				mindist = dist
		else:
			odds += 1
	if odds > 0:
		print(evens)
	elif evens > 0:
		print(int(log2(mindist) + evens - 1))


from math import log2
for _ in range(int(input())):
	x = int(input())
	y = list(map(int, input().split()))
	even = 0
	k = []
	for i in range(x):
		if y[i] % 2 == 0:
			even += 1
		k.append(y[i] - (y[i] & y[i] - 1))
	if even == 0:
		print(0)
	elif x > even > 0:
		print(even)
	else:
		print(int(log2(min(k))) + x - 1)


t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	num_odd = 0
	num_even = 0
	for x in a:
		if x % 2:
			num_odd += 1
	if num_odd == 0:
		m = 1000000000.0 + 8
		for x in a:
			y = x & -x
			m = min(m, y)
		k = 0
		while m % 2 == 0:
			m //= 2
			k += 1
		print(n + k - 1)
	else:
		print(n - num_odd)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))

	def ggcd(x, y):
		while y:
			(x, y) = (y, x % y)
		return x
	(e, c) = (0, 0)
	g = a[0]
	for x in a:
		if x % 2 == 0:
			g = ggcd(g, x)
			e += 1
	while g % 2 == 0:
		c += 1
		g /= 2
	if e == 0:
		print(0)
	elif e < n:
		print(e)
	else:
		print(e + c - 1)


from math import ceil, floor, log2

def ffs(x):
	return (x & -x).bit_length() - 1
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	q = set()
	a = 31
	(k, w) = (0, 0)
	for i in range(n):
		if l[i] % 2 == 0:
			k += 1
			if ffs(l[i]) < a:
				a = ffs(l[i])
		else:
			w = 1
		(e, f) = (0, 0)
	t = a + k - 1
	if w == 1:
		t = min(k, t)
	print(t)


import math
for _ in range(int(input())):
	n = int(input())
	x = [*map(int, input().split())]
	evenStack = []
	oddStack = []
	for y in x:
		(evenStack if y & 1 != 1 else oddStack).append(int(math.log2(y & -y) - 1))
	ans = len(evenStack) + (min(evenStack) if not oddStack else 0)
	print(ans)


n = int(input())

def ctz(v):
	return (v & -v).bit_length() - 1
for _ in range(n):
	length = int(input())
	no_odd = 0
	numbers = list(map(int, input().split()))
	even_numbers = []
	ret = 0
	for num in numbers:
		if num % 2 == 1:
			no_odd += 1
		else:
			even_numbers.append(num)
	if no_odd > 0:
		ret = length - no_odd
	else:
		count = 32
		for num in even_numbers:
			count = min(count, ctz(num))
		ret = count + len(even_numbers) - 1
	print(ret)


import math

def func(li, n):
	if n == 0:
		return
	c = 0
	a = 1000
	for x in li:
		if x % 2 == 1:
			c = c + 1
	e = n - c
	if c >= 1:
		return e
	for i in range(n):
		x = li[i]
		a = int(min(a, math.log2(x & -x)))
	return a + n - 1
t = int(input())
while t > 0:
	n = int(input())
	li = [int(x) for x in input().split()]
	print(func(li, n))
	t = t - 1


import math
t = int(input())
for _ in range(t):
	n = int(input())
	data = list(map(int, input().split()))
	odds = 0
	evens = 0
	quickestEven = 10000000000000000000
	for x in data:
		if x % 2 == 0:
			evens += 1
			quickestEven = min(quickestEven, math.log2(x & -x))
		else:
			odds += 1
	if odds > 0:
		print(evens)
	else:
		print(int(evens + quickestEven - 1))


import math
t = int(input())
for i in range(0, t):
	n = int(input())
	a = [int(x) for x in input().split(' ')]
	c = 0
	m = float('inf')
	for i in a:
		if i % 2 == 1:
			c += 1
		m = min(m, int(math.log2(i & -i)))
	if c > 0:
		print(n - c)
	else:
		print(n - 1 + m)


t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	evens = list(filter(lambda x: x % 2 == 0, a))
	nodds = n - len(evens)
	nevens = n - nodds
	if nodds != 0:
		print(nevens)
	else:
		num2s = list(map(lambda x: bin(x)[2:][::-1].index('1'), evens))
		print(min(num2s) + nevens - 1)


import math
for _ in range(int(input())):
	n = int(input())
	(cnt, a) = (0, 32)
	line = list(map(int, input().split()))
	for num in line:
		if num & 1 == 0:
			cnt += 1
			a = min(a, math.log2(num & -num))
	if cnt == n:
		print(cnt - 1 + int(a))
	else:
		print(cnt)


import math
import sys
for _ in range(int(input())):
	x = int(input())
	arr = list(map(int, sys.stdin.readline().split()))
	m = math.inf
	even = 0
	odd = 0
	for num in arr:
		if num % 2 == 0:
			even += 1
		else:
			odd += 1
	if odd > 0:
		print(even)
	else:
		m = math.inf
		for num in arr:
			if num % 2 == 0:
				m = min(m, (num & -num).bit_length() - 1)
		print(even - 1 + m)


import math

def highestPowerOf2(n):
	return n & ~(n - 1)

def magic(A):
	even = 0
	odd = 0
	count = 0
	c = math.inf
	for j in range(len(A)):
		count = 0
		if A[j] % 2 == 0:
			even += 1
			count = int(math.log2(highestPowerOf2(A[j])))
			c = min(c, count)
		else:
			odd += 1
	if odd > 0:
		return even
	else:
		return c + even - 1
t = int(input())
for i in range(t):
	n = int(input())
	A = list(map(int, input().split()))
	count = magic(A)
	print(count)


t = int(input())
for _ in range(t):
	input()
	a = [int(x) for x in input().split()]
	even_num = []
	num_odd = 0
	num_even = 0
	for x in a:
		if x % 2:
			num_odd += 1
		else:
			even_num.append(x)
			num_even += 1
	if num_odd == 0:
		m = 1000000000.0 + 7
		for x in a:
			y = x & -x
			m = min(m, y)
		k = -1
		for i in range(32):
			if m & 1 << i:
				k = i
				break
		print(k + num_even - 1)
	else:
		print(num_even)


for _ in range(int(input())):
	n = int(input())
	arr = [int(a) for a in input().split()]
	count = 0
	for num in arr:
		count += num % 2
	if count:
		print(n - count)
	else:
		s = ['{:b}'.format(b)[::-1] for b in arr]
		s = [c.index('1') for c in s]
		print(min(s) + n - 1)


t = int(input())
while t:
	t -= 1
	n = input()
	a = list(map(int, input().split(' ')))
	u = sum(map(lambda x: x & 1, a))
	if u:
		print(len(a) - u)
	else:
		a_ = []
		for x in a:
			bx = bin(x).split('b')[1]
			a_.append(len(bx) - 1 - bx.rfind('1'))
		print(min(a_) + len(a) - 1)


for _ in range(int(input())):
	n = input()
	arr = list(map(int, input().split(' ')))
	u = sum(map(lambda x: x & 1, arr))
	if u:
		print(len(arr) - u)
	else:
		arr2 = []
		for x in arr:
			bx = bin(x).split('b')[1]
			arr2.append(len(bx) - 1 - bx.rfind('1'))
		print(min(arr2) + len(arr) - 1)


from math import inf
for _ in range(int(input())):
	n = int(input())
	lst = [i for i in map(int, input().split()) if i % 2 == 0]
	m = len(lst)
	if m == 0:
		print(0)
	elif m < n:
		print(m)
	else:
		mi = inf
		for i in lst:
			e = bin(i)[::-1].index('1')
			mi = min(mi, e)
		print(mi + m - 1)


import math

def solve():
	n = int(input())
	l = list(map(int, input().split()))
	oe = [0, 0]
	for val in l:
		oe[val % 2] += 1
	if oe[1] > 0:
		return oe[0]
	else:
		min_shift = 1e+20
		for val in l:
			one = val ^ val - 1
			shift = one ^ one >> 1
			min_shift = min(min_shift, int(math.log2(shift)))
		ans = min_shift
		oe[0] -= 1
		return ans + oe[0]

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


for _ in range(int(input())):
	N = int(input())
	nums = list(map(int, input().split()))
	evens = 0
	odd_flg = False
	min_step = 30
	for num in nums:
		step = len(bin((num ^ num - 1) + 1)) - 4
		min_step = min(min_step, step)
		if step == 0:
			odd_flg = True
		else:
			evens += 1
	if odd_flg:
		print(evens)
	else:
		print(evens + min_step - 1)


import sys
input = sys.stdin.readline
T = int(input())
for testcase in range(1, T + 1):
	n = int(input())
	aa = list(map(int, input().split()))
	odds = 0
	besteven = 50
	for a in aa:
		if a % 2 != 0:
			odds += 1
		else:
			b = '0' + bin(a)[2:]
			l = len(b)
			right1 = b.rfind('1')
			num0 = l - right1
			if num0 < besteven:
				besteven = num0
	evens = n - odds
	result = evens
	if odds == 0:
		result += besteven - 2
	print(result)


for _ in range(int(input())):
	n = int(input())
	c = 0
	c0 = 40
	for x in map(int, input().split()):
		if x % 2:
			c += 1
		else:
			b = bin(x)
			c0 = min(c0, len(b) - len(b.rstrip('0')))
	if c > 0:
		print(n - c)
	else:
		print(c0 + n - 1)


from math import log2
for t in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	odd = 0
	teven = 0
	oeven = 10000000000000000000
	for i in l:
		if i % 2 == 0:
			st = str(bin(i))
			st = st[::-1]
			oeven = min(oeven, st.index('1'))
		else:
			odd += 1
	if odd >= 1:
		print(n - odd)
	else:
		print(oeven + (n - 1))


import math
for i in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split(' ')))
	(even, odd) = (0, 0)
	for value in arr:
		if value % 2 == 0:
			even += 1
		else:
			odd += 1
	ans = 0
	if odd != 0:
		ans = even
	else:
		min_op = 10 ** 9
		for value in arr:
			t1 = value - (value & value - 1)
			op = math.log(t1, 2)
			min_op = min(min_op, op)
		ans += min_op + even - 1
	print(int(ans))


for t in range(int(input())):
	n = int(input())
	l = [*(int(x) for x in input().split() if int(x) % 2 == 0)]
	m = len(l)
	if m == 0:
		print(0)
	elif m < n:
		print(len(l))
	else:
		mi = 10 ** 11
		for i in l:
			e = bin(i)[::-1].index('1')
			mi = min(mi, e)
		print(mi + m - 1)


t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(i) for i in input().split()]
	o = 0
	e = 0
	E = []
	for i in a:
		if i % 2 == 1:
			o += 1
		else:
			e += 1
			E.append(i)
	if o > 0:
		f = e
	else:
		f = e - 1
		min = 10000000
		for i in E:
			x = bin(i)[2:]
			j = x[::-1].index('1')
			if j < min:
				min = j
		f += min
	print(f)


T = int(input())
while T:
	T -= 1
	n = int(input())
	l = [int(x) for x in input().split()]
	ans = float('inf')
	cnt = 0
	for (i, x) in enumerate(l):
		num = 0
		if x % 2 == 1:
			cnt += 1
		bx = bin(x)[2:]
		num = len(bx) - bx.rfind('1') - 1
		ans = num if num < ans else ans
	print(n - cnt if ans == 0 else ans + n - 1)


from sys import stdin
from math import log, floor, ceil, gcd
inp = lambda : int(stdin.readline())

def ra(typ):
	return list(map(typ, stdin.readline().split()))

def rv(typ):
	return map(typ, stdin.readline().split())

def main():
	for _ in range(inp()):
		n = inp()
		a = ra(int)
		(odd, even) = (0, 0)
		for i in a:
			if i & 1 == 1:
				odd += 1
			else:
				even += 1
		if odd > 0:
			print(even)
		else:
			x = 9999999
			for i in a:
				if x == 1:
					break
				b = bin(i)
				b1 = bin(i).rstrip('0')
				x = min(x, len(b) - len(b1))
			print(even + x - 1)
main()


t = int(input())
for j in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	mn = 100
	n1 = 0
	n2 = 0
	for i in range(n):
		if a[i] % 2 != 0:
			n1 = 1
		else:
			n2 += 1
			st = bin(a[i])
			st = st[::-1]
			k = st.find('1')
			if k < mn:
				mn = k
		if n1 == 1:
			ans = n2
		else:
			ans = n2 + mn - 1
	print(ans)


t = int(input())
while t:
	n = int(input())
	l = list(map(int, input().split()))
	co = 0
	ce = 0
	le = []
	for i in range(n):
		if l[i] % 2 == 0:
			ce += 1
			le.append(l[i])
		else:
			co += 1
	if co != 0:
		print(ce)
	else:
		for i in range(len(le)):
			s = bin(l[i])[2:]
			s = s[::-1]
			f = s.index('1')
			l[i] = f
		print(min(l) + ce - 1)
	t -= 1


def solve():
	n = int(input())
	a = [int(e) for e in input().split()]
	(even, min2) = (0, 33)
	for x in a:
		if x % 2 == 0:
			even += 1
		if x % 2 == 1:
			min2 = 0
			continue
		man = str(bin(x))
		min2 = min(len(man) - len(man.rstrip('0')), min2)
	print(min2 + even - (1 if min2 > 0 else 0))
	return

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


for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	even = 0
	odd = 0
	e = []
	for c in a:
		if c & 1:
			odd += 1
		else:
			even += 1
			e.append(c)
	if odd:
		print(even)
	else:
		T = True
		for i in range(e.__len__()):
			e[i] = len(bin(e[i])[2:].split('1')[-1])
		num = min(e)
		print(even - 1 + num)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	fil = []
	flag = False
	for i in l:
		if i % 2 == 0:
			b = list(bin(i)[2:])
			b.reverse()
			fil.append(b.index('1'))
		else:
			flag = True
	if len(fil) == 0:
		print(0)
	else:
		x = min(fil)
		if flag:
			x = 1
		print(x + len(fil) - 1)


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	l1 = []
	l2 = []
	p = 100000000
	for i in range(n):
		if l[i] % 2 == 0:
			l1.append(l[i])
		else:
			l2.append(l[i])
	l3 = []
	if len(l2) > 0:
		print(len(l1))
		continue
	for i in l1:
		z = bin(i)
		z = z[2:]
		z = z[::-1]
		q = z.index('1')
		p = min(p, q)
	print(p + len(l1) - 1)


import math
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	flag = True
	for x in a:
		if x % 2 == 1:
			flag = False
			break
	mx = 32
	nod = 0
	for x in a:
		if x % 2 == 1:
			nod += 1
		elif flag:
			while math.ceil(x / math.pow(2, mx)) != math.floor(x / math.pow(2, mx)):
				mx -= 1
	if flag == False:
		print(n - nod)
	else:
		print(mx + n - 1)


for _ in range(int(input())):
	n = int(input())
	(even, odd) = (0, 0)
	num = list(map(int, input().split()))
	for i in range(n):
		if num[i] % 2 == 0:
			even += 1
	odd = n - even
	if even == 0:
		print(0)
	elif odd != 0:
		print(even)
	else:
		ans = even - 1
		x = sum(num)
		while x / 2 == int(x / 2):
			x = x / 2
			ans += 1
		ans1 = 1000000000
		for i in range(n):
			x = str(bin(num[i]))
			x = x[::-1]
			z = x.find('1')
			ans1 = min(ans1, z)
		ans1 = ans1 + even - 1
		print(min(ans, ans1))


from cmath import sqrt
from collections import defaultdict
from math import *
import sys
from typing import Counter
input = sys.stdin.readline
for _ in range(int(input())):
	n = list(map(int, input().split()))[0]
	a = list(map(int, input().split()))
	odd = []
	even = []
	for i in a:
		if i & 1:
			odd.append(i)
		else:
			even.append(i)
	if not even:
		print(0)
	elif odd:
		print(len(even))
	else:
		minn = float('inf')
		c = 40
		for i in even:
			c = min(c, bin(i)[2:][::-1].find('1'))
			minn = min(minn, c)
		print(minn + len(even) - 1)


def f(n):
	k = 0
	while n != 1:
		n /= 2
		k += 1
		if n % 2 == 1:
			break
	return k
t = int(input())
for i in range(t):
	n = int(input())
	a = [int(i) for i in input().split()]
	a.sort()
	b = []
	c = set()
	for el in a:
		if el % 2 == 0:
			b.append(el)
			c.add(el)
	if len(b) != len(a):
		m = len(b)
	else:
		m = 100000000
		for el in c:
			m = min(m, f(el))
		m = m + len(b) - 1
	print(m)


def main():
	n = int(input())
	arr = list(map(int, input().split()))
	odd = 0
	even = 0
	for z in arr:
		if z % 2:
			odd += 1
	even = n - odd
	if odd > 0:
		return even
	pos = {}
	for z in arr:
		b = bin(z)
		b = b[::-1]
		for i in range(len(b)):
			if b[i] == '1':
				if i not in pos:
					pos[i] = 0
				pos[i] += 1
				break
	srt = list(pos.keys())
	srt.sort()
	ans = 0
	sm = srt[0]
	freq = pos[sm]
	ans += sm
	ans += n - 1
	return ans
	ans += n - pos[srt[0]]
	if freq % 2:
		ans += freq - 1
		ans += sm
		return ans
	else:
		ans += freq - 2
		pre = sum(arr)
		b = bin(pre)
		b = b[::-1]
		for i in range(len(b)):
			if b == '1':
				break
		addon = min(2 * sm, 1 + i)
		ans += addon
		return ans
		if sm > 2:
			ans += 1
			ans += sm + 1
			return ans
		else:
			ans += 2 * sm
			return ans
	return ans
for _ in range(int(input())):
	print(main())


t = int(input())

def zcount(n):
	c = 0
	for i in str(bin(n))[::-1]:
		if i == '0':
			c += 1
		else:
			return c
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split(' ')))
	b = []
	c = []
	for i in a:
		if i % 2 == 0:
			c.append(zcount(i))
			b.append(i)
	if len(b) != n:
		print(len(b))
	else:
		print(min(c) + len(b) - 1)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	c = sum((x % 2 == 1 for x in l))
	r = 10000000000.0
	if c:
		print(n - c)
		continue
	for x in set(l):
		cnt = 0
		while x % 2 == 0:
			x = x // 2
			cnt += 1
		r = min(r, cnt)
	print(r + (n - c - 1))


t = int(input())
for _ in range(t):
	n = int(input())
	tokens = [int(x) for x in input().split()]
	L = len(tokens)
	O = sum((x % 2 for x in tokens))
	if O > 0:
		print(L - O)
	else:
		mindiv = -1
		for tok in set(tokens):
			d = 0
			while tok % 2 == 0:
				tok //= 2
				d += 1
			if mindiv == -1 or mindiv > d:
				mindiv = d
		y = mindiv + L - 1
		print(y)


import sys
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	c = [0 if i % 2 == 0 else 1 for i in l]
	d = n - c.count(1)
	if d != n:
		print(d)
	else:
		ma = sys.maxsize
		for m in set(l):
			k = 0
			while m % 2 == 0:
				m = m / 2
				k += 1
			ma = min(ma, k)
		print(ma + n - 1)


x = int(input())

def cal(n, arr):
	t = float('inf')
	evn = 0
	for i in range(n):
		if arr[i] % 2 == 0:
			evn += 1
	if evn == 0:
		return 0
	if evn < n:
		return evn
	for i in range(n):
		p = bin(arr[i])
		k = -1
		for j in range(len(p) - 1, -1, -1):
			if p[j] != '0':
				k = len(p) - 1 - j
				break
		if k == 1:
			return n
		t = min(t, n - 1 + k)
	return t
for jj in range(x):
	n = int(input())
	arr = [int(i) for i in input().split(' ')]
	print(cal(n, arr))


import math
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	c = 0
	for i in l:
		if i % 2 != 0:
			c += 1
	if c > 0:
		print(n - c)
	else:
		s = set(l)
		s1 = set()
		for i in s:
			j = 0
			k = i
			while k % 2 == 0:
				k /= 2
				j += 1
			s1.add(j)
		print(min(s1) + n - 1)


t = int(input())
a = []
for i in range(t):
	h = input()
	a += [list(map(int, input().split()))]
for ela in a:
	chet = []
	necht = []
	for el in ela:
		if el % 2 == 1:
			necht += [el]
		else:
			chet += [el]
	if necht:
		print(len(chet))
	else:
		sc = list(set(chet))
		go = True
		c = 0
		while go:
			c += 1
			for i in range(len(sc)):
				sc[i] = sc[i] / 2
				if sc[i] % 2 == 1:
					print(len(chet) - 1 + c)
					go = False
					break


n = int(input())
for _ in range(n):
	k = int(input())
	nums = list(map(int, input().split()))
	odds = 0
	for x in nums:
		if x % 2 == 1:
			odds += 1
	if odds > 0:
		print(k - odds)
		continue
	least = 100
	seen = {}
	for x in nums:
		if x in seen:
			continue
		j = x
		count = 0
		while j % 2 == 0:
			count += 1
			j = j / 2
		least = min(least, count)
		seen[x] = count
	print(least + k - 1)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	oddCount = 0
	for i in a:
		if not i % 2 == 0:
			oddCount += 1
	if oddCount > 0:
		print(n - oddCount)
	else:
		a = set(a)
		mp = float('inf')
		for i in a:
			x = i
			c = 0
			while x % 2 == 0 and c < mp:
				x //= 2
				c += 1
			mp = min(mp, c)
		print(n - 1 + mp)


t = int(input(''))
for z in range(t):
	n = int(input(''))
	c = 0
	d = 0
	e = 0
	t = 0
	b = []
	a = list(map(int, input('').split()))[:n]
	for x in a:
		if x % 2 != 0:
			c += 1
		else:
			d += 1
	if d == 0:
		print(0)
	elif c >= 1:
		print(d)
	else:
		cl = set(a)
		cl = list(cl)
		for p in cl:
			t = 0
			while t != 1:
				if p % 2 == 0:
					p = p / 2
					e += 1
				else:
					t = 1
			b.append(e)
			e = 0
		print(min(b) + d - 1)


t = int(input())
for _ in range(t):
	(n,) = map(int, input().split())
	a = list(map(int, input().split()))
	o = 0
	for i in a:
		if i % 2 != 0:
			o += 1
	if o > 0:
		print(n - o)
		continue
	mp = float('inf')
	a = set(a)
	for i in a:
		x = i
		p = 0
		while x % 2 == 0 and p < mp:
			x //= 2
			p += 1
		mp = min(mp, p)
	print(n - 1 + mp)


for time in range(int(input())):
	n = int(input())
	j = float('inf')
	nums = list(map(int, input().split()))
	k = 0
	numbers = set()
	for j in nums:
		if j % 2 == 0:
			k += 1
	if k != n:
		print(k)
		continue
	best = float('inf')
	for j in nums:
		if j in numbers:
			continue
		numbers.add(j)
		l = 0
		while l < best and j % 2 == 0:
			j = j // 2
			l += 1
		if best > l:
			best = l
	print(best + k - 1)


def odd(x: int) -> bool:
	return x & 1

def div2(x: int) -> int:
	d = x & -x
	cnt = 0
	while d > 1:
		cnt += 1
		d >>= 1
	return cnt
for _ in range(int(input())):
	_ = input()
	a = list(map(int, input().split()))
	evens = [x for x in a if not odd(x)]
	odds = [x for x in a if odd(x)]
	if len(evens) == 0:
		print(0)
	elif len(evens) > len(odds):
		if len(odds) != 0:
			print(len(evens))
		else:
			tmp = div2(min(evens, key=div2)) + len(evens) - 1
			print(tmp)
	else:
		print(len(evens))


n = int(input())
datas = []
for i in range(n):
	l = int(input())
	data = input().split()
	numbers = [int(n) for n in data]
	datas.append(numbers)

def solve1(n):
	for i in range(32):
		if n >> i & 1:
			return i

def solve(data):
	even_count = 0
	odd_count = 0
	m = None
	for n in data:
		if n % 2 == 0:
			even_count += 1
			r = solve1(n)
			if m is None:
				m = r
			else:
				m = min(m, r)
		else:
			odd_count += 1
	if odd_count:
		print(even_count)
	else:
		print(m + even_count - 1)
for data in datas:
	solve(data)


def decimalToBinary(n):
	return bin(n).replace('0b', '')

def helper(x):
	x_ = decimalToBinary(x)
	k = len(x_)
	var = len(x_) - 1
	k -= 1
	while k >= 0:
		if x_[k] == '1':
			return var - k
		else:
			k -= 1

def min_operations(x, list):
	num_even = 0
	for i in range(x):
		if list[i] % 2 == 0:
			num_even += 1
	if num_even == 0:
		return 0
	elif num_even < x:
		return num_even
	else:
		num_operations = []
		for i in range(x):
			var = helper(list[i])
			num_operations.append(var)
		temp = min(num_operations)
		ans = x - 1 + temp
		return ans
n = int(input())
for i in range(n):
	x = int(input())
	l = list(map(int, input().split()))
	print(min_operations(x, 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())

def func(nums, count):
	i = 0
	found = False
	oddNums = [n for n in nums if n % 2 == 0]
	if not oddNums:
		return 0
	if len(oddNums) != len(nums):
		return len(oddNums)
	while not found:
		for num in nums:
			if num & 1 << i:
				found = True
				break
		if not found:
			i += 1
	return i + len(oddNums) - 1
numberOfInput = inp()
for i in range(numberOfInput):
	try:
		a = inp()
		b = inlt()
		print(func(b, 0))
	except:
		break


le = int(input())
s = []
for y in range(le):
	k = int(input())
	l = [int(n) for n in input().split()]
	ev = 0
	for m in l:
		if m % 2 == 0:
			ev += 1
	if ev < k:
		s.append(ev)
	elif ev == k:
		rmin = []
		for m in l:
			q = bin(m)[::-1]
			for i in range(len(q)):
				if q[i] == '1':
					rmin.append(i)
					break
		s.append(min(rmin) + k - 1)
for i in s:
	print(i)


import sys

def solve():
	odd = False
	even = 0
	val = sys.maxsize
	for i in range(n):
		if arr[i] % 2:
			odd = True
		else:
			even += 1
			temp = arr[i]
			count = 0
			while temp & 1 == 0:
				count += 1
				temp >>= 1
			val = min(val, count)
	if odd:
		return even
	val += even - 1
	return val
T = int(input())
for t in range(T):
	n = int(input())
	arr = list(map(int, input().split()))
	ans = solve()
	print(ans)


def binc(n):
	return bin(n).replace('0b', '')
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split(' ')))
	count = 0
	k = []
	ind = []
	for i in range(n):
		if l[i] % 2 != 0:
			count += 1
	if count == 0:
		for i in range(n):
			k.append(list(str(binc(l[i]))))
			ind.append(k[i][::-1].index('1'))
		print(min(ind) + n - 1)
	else:
		print(n - count)


def work(a):
	(c, b) = (0, 0)
	for o in a:
		if o & 1:
			c += 1
		else:
			b += 1
	if c != 0:
		print(b)
	else:
		mink = 1000000000.0 + 1
		for o in a:
			k = 0
			while not o & 1:
				k += 1
				o //= 2
			mink = min(mink, k)
		print(mink + b - 1)
n = int(input())
while n:
	n -= 1
	input()
	a = list(map(int, input().split()))
	work(a)


t = int(input())
for ran in range(t):
	k = int(input())
	li = list(map(int, input().split()))
	even = 0
	odd = 0
	l3 = []
	for x in li:
		if x % 2 == 0:
			even += 1
		else:
			odd += 1
		l3.append(bin(x)[2:])
	if odd == 0:
		l4 = []
		for y in l3:
			for z in range(-1, -len(y) - 1, -1):
				if y[z] == '1':
					l4.append(-z - 1)
					break
		minn = 10 ** 10
		for x in l4:
			if x < minn:
				minn = x
		print(even + minn - 1)
	else:
		print(even)


import io, os

def ri():
	return int(input().strip())

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

def Solve():
	n = ri()
	a = rl()
	cnt = 0
	for x in a:
		cnt += x & 1
	if cnt != 0:
		print(n - cnt)
		return
	ans = 1000000000.0
	for x in a:
		tmp = 0
		while x & 1 == 0:
			tmp += 1
			x >>= 1
		ans = min(ans, tmp)
	print(ans + n - 1)
T = ri()
while T:
	T -= 1
	Solve()