You are given an array of positive integers $a_1, a_2, \ldots, a_n$.

Make the product of all the numbers in the array (that is, $a_1 \cdot a_2 \cdot \ldots \cdot a_n$) divisible by $2^n$.

You can perform the following operation as many times as you like:

select an arbitrary index $i$ ($1 \leq i \leq n$) and replace the value $a_i$ with $a_i=a_i \cdot i$.

You cannot apply the operation repeatedly to a single index. In other words, all selected values of $i$ must be different.

Find the smallest number of operations you need to perform to make the product of all the elements in the array divisible by $2^n$. Note that such a set of operations does not always exist.


-----Input-----

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

Then the descriptions of the input data sets follow.

The first line of each test case contains a single integer $n$ ($1 \leq n \leq 2 \cdot 10^5$) — the length of array $a$.

The second line of each test case contains exactly $n$ integers: $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^9$).

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


-----Output-----

For each test case, print the least number of operations to make the product of all numbers in the array divisible by $2^n$. If the answer does not exist, print -1.


-----Examples-----

Input
6
1
2
2
3 2
3
10 6 11
4
13 17 1 1
5
1 1 12 1 1
6
20 7 14 18 3 5
Output
0
1
1
-1
2
1


-----Note-----

In the first test case, the product of all elements is initially $2$, so no operations needed.

In the second test case, the product of elements initially equals $6$. We can apply the operation for $i = 2$, and then $a_2$ becomes $2\cdot2=4$, and the product of numbers becomes $3\cdot4=12$, and this product of numbers is divided by $2^n=2^2=4$.

In the fourth test case, even if we apply all possible operations, we still cannot make the product of numbers divisible by $2^n$  — it will be $(13\cdot1)\cdot(17\cdot2)\cdot(1\cdot3)\cdot(1\cdot4)=5304$, which does not divide by $2^n=2^4=16$.

In the fifth test case, we can apply operations for $i = 2$ and $i = 4$.

Source: codeforces | Difficulty: EASY
Tags: Sorting

Mathematics

Greedy algorithms


Solutions:
def count_2(ai):
	res = 0
	while not ai % 2:
		ai = ai // 2
		res += 1
	return res

def output(a, n):
	n2 = 0
	res = 0
	for ai in a:
		n2 += count_2(ai)
		if n2 > n:
			return 0
	nearest_2 = 1
	n1 = n
	while n1 >= 2 ** nearest_2:
		nearest_2 += 1
	nearest_2 -= 1
	n_2 = 1
	t_selected = 0
	while n2 < n and nearest_2 > 0:
		if n_2 > 0:
			n2 += nearest_2
			n_2 -= 1
			res += 1
			t_selected += 1
		else:
			nearest_2 -= 1
			n_2 = n // 2 ** nearest_2 - t_selected
	if n2 < n:
		return -1
	return res
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	res = output(a, n)
	print(res)


def solve(n, arr):
	dp = [0, 0]
	twos = 0
	for val in arr:
		num = val
		while not num % 2:
			num //= 2
			twos += 1
			if twos == n:
				return 0
	for i in range(2, n + 1):
		if i % 2:
			dp.append(0)
		else:
			dp.append(dp[i // 2] + 1)
	dp.sort(reverse=True)
	ans = 0
	for val in dp:
		ans += 1
		twos += val
		if twos >= n:
			return ans
	return -1
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	print(solve(n, arr))


def dvo(x):
	if x % 2 == 0:
		return dvo(x // 2) + 1
	else:
		return 0
for i in range(int(input())):
	N = n = int(input())
	a = input().split()
	otv = 0
	op = 1
	for k in a:
		k = int(k)
		n -= dvo(k)
		if n <= 0:
			break
	if n > 0:
		som = []
		for x in range(2, N + 1, 2):
			som += [dvo(x)]
		som.sort()
		som.reverse()
		while n > 0 and otv < len(som):
			n -= som[otv]
			otv += 1
	if n > 0:
		print(-1)
	else:
		print(otv)


from typing import Counter
import sys
input = sys.stdin.readline

def print(*args, end='\n', sep=' ') -> None:
	sys.stdout.write(sep.join(map(str, args)) + end)
t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	col = 0
	for i in range(n):
		while l[i] % 2 == 0:
			l[i] >>= 1
			col += 1
		if col >= n:
			break
	if col >= n:
		print(0)
		continue
	col_2 = 0
	d = 1
	while d * 2 <= n:
		col_2 += 1
		d *= 2
	ans = 0
	while d != 1 and col < n:
		for _ in range(d, n + 1, 2 * d):
			col += col_2
			ans += 1
			if col >= n:
				break
		d //= 2
		col_2 -= 1
	if col >= n:
		print(ans)
	else:
		print(-1)


import math
testcases = int(input())
while testcases > 0:
	testcases -= 1
	n = int(input())
	twopower = 0
	lst = [int(x) for x in input().split()]
	for element in lst:
		twopower += int(math.log(element & ~(element - 1), 2))
	if twopower >= n:
		print(0)
		continue
	balance = n - twopower
	maxpower = int(math.log(n, 2))
	temporary = 0
	floordiv_value = 0
	answer = 0
	while maxpower > 0:
		floordiv_value = n // pow(2, maxpower)
		current = int(floordiv_value - temporary)
		if current * maxpower >= balance:
			answer += float(balance) / maxpower
			balance = 0
			answer = math.ceil(answer)
			break
		temporary = floordiv_value
		answer += current
		balance -= current * maxpower
		maxpower -= 1
	if balance > 0:
		print(-1)
	else:
		print(int(answer))


def gs(x):
	to = 0
	while x % 2 == 0:
		to += 1
		x /= 2
	return to
t = int(input())
for i in range(t):
	n = int(input())
	nums = [int(temp) for temp in input().split()]
	odd = 0
	jl = [0] * (n + 1)
	flag = 0
	k = 0
	for j in range(n - 1, -1, -1):
		odd += gs(nums[j])
		if odd >= n:
			flag = 1
			break
	if flag == 0:
		for i in range(1, n + 1):
			jl[i] = gs(i)
		jl.sort()
		for i in range(n, 0, -1):
			odd += jl[i]
			k += 1
			if odd >= n:
				flag = 1
				break
		if flag == 1:
			print(k)
		else:
			print(-1)
	else:
		print(k)


k = int(input())
for l in range(k):
	n = int(input())
	a = list(map(int, input().split()))
	temp = n
	flag = 0
	for i in range(n):
		b = a[i]
		while True:
			if b % 2 == 0:
				temp -= 1
				b /= 2
			else:
				break
		if temp <= 0:
			print(0)
			flag = 1
			break
	if flag == 0:
		arr = []
		for i in range(1, n + 1):
			cnt = 0
			c = i
			while True:
				if c % 2 == 0:
					cnt += 1
					c = c / 2
				else:
					break
			if cnt > 0:
				arr.append(cnt)
		arr = sorted(arr)
		arr = arr[::-1]
		ans = 0
		for i in range(len(arr)):
			temp -= arr[i]
			ans += 1
			if temp <= 0:
				print(ans)
				flag = 1
				break
		if temp > 0:
			print(-1)


import math
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	mmm = []
	if 0 in a:
		print(0)
		continue
	k2 = 0
	op = 0
	f = 0
	for j in range(n):
		while a[j] % 2 == 0:
			k2 += 1
			a[j] //= 2
			if k2 >= n:
				f = 1
				break
		if f:
			break
	if k2 < n:
		for j in range(n - 1, 0, -1):
			m = 0
			x = j + 1
			while x % 2 == 0:
				m += 1
				x //= 2
			mmm.append(m)
		mmm.sort(reverse=True)
		for el in mmm:
			k2 += el
			op += 1
			if k2 >= n:
				break
	if k2 >= n:
		print(op)
	else:
		print(-1)


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

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

	def answer(n, a):
		c = 0
		l = []
		for i in range(n):
			c = c + factor(a[i])
			l.append(factor(i + 1))
			if c >= n:
				return 0
		d = 0
		l.sort()
		x = n - 1
		while x >= 0:
			c = c + l[x]
			d = d + 1
			x = x - 1
			if c >= n:
				return d
		return -1
	print(answer(n, a))


def count_2(x):
	c = 0
	while x % 2 == 0:
		c += 1
		x //= 2
	return c
for _ in range(int(input())):
	l = []
	n = int(input())
	a = [int(i) for i in input().split()]
	(already, op) = (0, 0)
	for (i, x) in enumerate(a):
		if already >= n:
			break
		already += count_2(x)
		op = count_2(i + 1)
		if op != 0:
			l.append(op)
	if already >= n:
		print(0)
		continue
	l.sort(reverse=True)
	n -= already
	c = 0
	for k in l:
		n -= k
		c += 1
		if n <= 0:
			break
	if n > 0:
		print(-1)
	else:
		print(c)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	nown = 0
	for i in range(n):
		while not a[i] & 1:
			nown += 1
			a[i] = a[i] >> 1
			if nown >= n:
				break
	if nown >= n:
		print(0)
		continue
	answer = 0
	step = 1
	maxn = 0
	while step < n:
		step = step * 2
		maxn += 1
	if step > n:
		step = step >> 1
		maxn -= 1
	if maxn <= 0:
		print(-1)
		continue
	while nown < n:
		unchet = 1
		while step * unchet <= n:
			nown += maxn
			answer += 1
			unchet += 2
			if nown >= n:
				break
		maxn -= 1
		step = step >> 1
		if maxn <= 0:
			break
	if nown >= n:
		print(answer)
		continue
	else:
		print(-1)
		continue


n = int(input())
for i in range(n):
	t = int(input())
	count = 0
	ans = 0
	k = 0
	dvoiki = []
	s = str(input()).split()
	s = [int(a) for a in s]
	for j in range(len(s)):
		if s[j] % 2 == 0:
			while s[j] % 2 == 0:
				if k == t:
					break
				s[j] = s[j] / 2
				k += 1
	if k < t:
		for j in range(len(s)):
			m = j + 1
			kolvo = 0
			if m % 2 == 0:
				while m % 2 == 0:
					m = m / 2
					kolvo += 1
				dvoiki.append(kolvo)
		dvoiki = sorted(dvoiki, reverse=True)
		for g in dvoiki:
			if k >= t:
				break
			k += g
			count += 1
		if k >= t:
			ans = count
		else:
			ans = -1
	else:
		ans = 0
	print(ans)


import math

def foo(n, ls):
	needs = n
	pows = []
	for (i, val) in enumerate(ls):
		ilog = int(math.log2(i + 1 & -(i + 1)))
		if ilog > 0:
			pows.append(ilog)
		vlog = int(math.log2(val & -val))
		needs -= vlog
	if needs <= 0:
		return 0
	pows.sort()
	ans = 0
	while needs > 0 and pows:
		needs -= pows.pop()
		ans += 1
	if needs > 0:
		return -1
	return ans
t = int(input())
for _ in range(t):
	n = int(input())
	ls = [int(i) for i in input().split()]
	print(foo(n, ls))


import math

def highestPowerOf2(n):
	return n & ~(n - 1)
for i in range(int(input())):
	n = int(input())
	arrI = list(map(int, input().split()))
	sumOfPowTwo = 0
	for i in arrI:
		sumOfPowTwo += math.log(highestPowerOf2(i), 2)
	sumOfPowTwo = int(sumOfPowTwo)
	if sumOfPowTwo >= n:
		print(0)
	else:
		arrPow2 = []
		for i in range(n):
			arrPow2.append(int(math.log(highestPowerOf2(i + 1), 2)))
		if sum(arrPow2) + sumOfPowTwo < n:
			print(-1)
		else:
			arrPow2.sort(reverse=True)
			for i in range(n):
				if sumOfPowTwo >= n:
					print(i)
					break
				else:
					sumOfPowTwo += arrPow2[i]


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split(' ')))
	cd = []
	c = 0
	for i in range(n):
		j = a[i]
		c += max((j & -j).bit_length() - 1, 0)
		cd.append(max((i + 1 & -(i + 1)).bit_length() - 1, 0))
	s = sum(cd)
	cd.sort(reverse=True)
	if c < n:
		if s >= n - c:
			k = n - c
			coun = 0
			for p in cd:
				if k >= p:
					k -= p
					coun += 1
					if k == 0:
						break
			print(coun)
		if s < n - c:
			print(-1)
	else:
		print(0)


from math import log2

def get_power_of_two(n):
	return int(log2(n & ~(n - 1)))
for _ in range(int(input())):
	n = int(input())
	array = list(map(int, input().split()))
	power_sum = 0
	extra_powers = []
	for (i, number) in enumerate(array):
		power_sum += get_power_of_two(number)
		if (extra_power := get_power_of_two(i + 1)):
			extra_powers.append(extra_power)
	extra_powers = sorted(extra_powers)
	operations = 0
	while power_sum < n:
		if len(extra_powers) == 0:
			operations = -1
			break
		power_sum += extra_powers.pop()
		operations += 1
	print(operations)


from math import *
for z in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	p = 0
	i = 1
	z = []
	while i <= n:
		b2 = bin(a[i - 1])
		y1 = len(b2) - b2.rfind('1') - 1
		b1 = bin(i)
		y2 = len(b1) - b1.rfind('1') - 1
		z.append(y2)
		p += y1
		i += 1
	p1 = bin(p)
	p = n - p
	z.sort()
	ans = 0
	try:
		while p > 0:
			p -= z.pop()
			ans += 1
		print(ans)
	except:
		print(-1)


from math import ceil
from math import sqrt
from collections import Counter

def hpt(el):
	p = 0
	while el % 2 ** p == 0:
		p += 1
	return p - 1
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	on = 0
	m = n
	for i in range(n):
		cal = hpt(l[i])
		m -= cal
		if m <= 0:
			on = 1
			break
	if on == 1:
		print(0)
	else:
		idx_ = []
		for i in range(2, n + 1, 2):
			idx_.append(i)
		pht = []
		for i in range(len(idx_)):
			cal = hpt(idx_[i])
			pht.append(cal)
		pht.sort()
		on2 = 0
		op = 0
		for i in range(1, len(pht) + 1):
			m -= pht[-i]
			if m <= 0:
				on2 = 1
				op += 1
				break
			op += 1
		if m <= 0:
			print(op)
		else:
			print(-1)


tc = int(input())
operations_list = [0] * 200000
for j in range(0, 2 * 10 ** 5):
	c_num = 2 * 10 ** 5 - j
	num_twos = 0
	while c_num % 2 == 0 and c_num != 0:
		num_twos += 1
		c_num = c_num / 2
	operations_list[2 * 10 ** 5 - j - 1] = num_twos
for z in range(0, tc):
	k = int(input())
	arr_copy = [0] * k
	for l in range(0, k):
		arr_copy[l] = operations_list[l]
	arr = [int(part) for part in input().split()]
	count = 0
	num_oper = -1
	for i in range(0, k):
		c_num = arr[i]
		while c_num % 2 == 0 and c_num != 0:
			count += 1
			c_num = c_num / 2
		if count >= k:
			num_oper = 0
			break
	if count < k:
		twos_needed = k - count
		arr_copy.sort(reverse=True)
		added_operations = 0
		for p in range(0, len(arr_copy)):
			twos_needed -= arr_copy[p]
			added_operations += 1
			if twos_needed <= 0:
				break
		if twos_needed <= 0:
			print(added_operations)
		else:
			print(-1)
	else:
		print(0)


import sys
sys.setrecursionlimit(200000)
import math
from collections import Counter
from collections import defaultdict
from collections import deque
input = sys.stdin.readline
from functools import lru_cache
import heapq

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())
power = []

@lru_cache(None)
def find(i):
	return 1 + find(i // 2) if i % 2 == 0 else 0
for i in range(1, 2 * 10 ** 5 + 1):
	power.append(find(i))
for _ in range(inp()):
	n = inp()
	arr = inlt()
	number = 0
	ans = 0
	for i in range(n):
		number += find(arr[i])
	if number >= n:
		print(ans)
		continue
	else:
		p = power[:n]
		p.sort(reverse=True)
		for i in range(n):
			ans += 1
			number += p[i]
			if number >= n:
				break
		print(ans) if number >= n else print(-1)


all_twos = {'1': 0, '2': 1}

def count_twos(n, memo={}):
	if n in memo.keys():
		return memo[n]
	else:
		if n % 2 == 0:
			memo[n] = 1 + count_twos(n / 2, memo)
			return memo[n]
		memo[n] = 0
		return memo[n]
t = int(input())
for a0 in range(t):
	n = int(input())
	total_twos = sum([count_twos(int(i), all_twos) for i in str(input()).strip().split()])
	if total_twos >= n:
		print(0)
	else:
		n_twos = [count_twos(i, all_twos) for i in range(1, n + 1)]
		n_twos.sort()
		(it, id) = (0, n - 1)
		while id >= 0 and total_twos < n:
			total_twos += n_twos[id]
			it += 1
			id -= 1
		if total_twos >= n:
			print(it)
		else:
			print(-1)


import functools
tem = [0] * 200001
su = [0] * 200001

@functools.lru_cache(None)
def cal(a):
	if a % 2 == 1:
		return 0
	else:
		return 1 + cal(a // 2)
for i in range(2, 200001):
	tem[i] = cal(i)
	su[i] = su[i - 1] + tem[i]
for jj in range(int(input())):
	n = int(input())
	arr = [int(i) for i in input().split()]
	c = 0
	for i in arr:
		c += cal(i)
	if c >= n:
		print(0)
	elif n - c > su[n]:
		print(-1)
	else:
		tt = sorted(tem[:n + 1], reverse=True)
		cap = n - c
		for i in range(n + 1):
			cap -= tt[i]
			if cap <= 0:
				print(i + 1)
				break


def numD2(n, mem):
	if n in mem:
		return mem[n]
	if n % 2:
		mem[n] = 0
		return 0
	else:
		mem[n] = numD2(n // 2, mem) + 1
		return mem[n]
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	resources = [(-1, i) for i in range(1, n + 1)]
	for i in range(n):
		(nb2, vi) = resources[i]
		if i > n // 2:
			break
		if nb2 == -1:
			if vi % 2 == 0:
				nb2 = 1
			else:
				nb2 = 0
			resources[i] = (nb2, vi)
			while vi <= n // 2:
				vi *= 2
				nb2 += 1
				resources[vi - 1] = (nb2, vi)
	resources = [i for i in resources if i[0] > 0]
	resources.sort()
	divided = 0
	memo = dict()
	for i in range(n):
		divided += numD2(a[i], memo)
	nbOp = 0
	while divided < n:
		if len(resources) == 0:
			print(-1)
			break
		(op, _) = resources.pop()
		nbOp += 1
		divided += op
	else:
		print(nbOp)


def bipo(a: int) -> int:
	po = 0
	while a % 2 == 0:
		po += 1
		a //= 2
	return po
for _ in range(int(input())):
	n = int(input())
	a = sum(list(map(lambda x: bipo(int(x)), input().split())))
	if n <= a:
		print(0)
		continue
	indices = [bipo(x) for x in range(1, n + 1)]
	indices.sort(reverse=True)
	op = 0
	while indices[op] and a < n:
		a += indices[op]
		op += 1
	if a < n:
		print(-1)
	else:
		print(op)


def p(n):
	(l, r) = (0, 1)
	while 2 ** r <= n:
		(l, r) = (r, r * 2)
	while r - l > 1:
		m = (l + r) // 2
		if 2 ** m <= n:
			l = m
		else:
			r = m
	return l

def one():
	n = int(input())
	a = list(map(int, input().split()))
	v = sorted((p(k & -k) for k in range(1, n + 1)))
	z = sum((p(e & -e) for e in a))
	c = 0
	while z < n and v:
		z += v.pop()
		c += 1
	print(c if v else -1)
t = int(input())
for i in range(t):
	one()


import sys
import math
import heapq
from functools import lru_cache
from collections import Counter
from collections import defaultdict
from collections import deque
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 count2s(num):
	count = 0
	while num % 2 == 0:
		count += 1
		num //= 2
	return count

def main():
	n = inp()
	array = inlt()
	twoCount = 0
	for num in array:
		twoCount += count2s(num)
	if n % 2 == 0:
		num = n
	else:
		num = n - 1
	countsOf2ByIndex = []
	for i in range(2, num + 1, 2):
		count = count2s(i)
		countsOf2ByIndex.append(count)
	countsOf2ByIndex.sort(reverse=True)
	needed = 0
	i = 0
	while twoCount < n and i < len(countsOf2ByIndex):
		twoCount += countsOf2ByIndex[i]
		i += 1
		needed += 1
	if twoCount >= n:
		print(needed)
	else:
		print(-1)
t = inp()
for _ in range(t):
	main()


from collections import deque
InputList = lambda Dtype: [Dtype(x) for x in input().split()]
from functools import lru_cache
from math import pi, log2

def solve():
	N = int(input())
	nums = InputList(int)

	def find_max_power_of_2(n):
		count = 0
		while n % 2 == 0:
			n //= 2
			count += 1
		return count
	used = set()
	have = sum((find_max_power_of_2(x) for x in nums))
	need = N - have
	if need <= 0:
		return 0
	cur = int(log2(N))
	ans = 0
	while need > 0 and cur >= 1:
		factor = 1
		candidate = 2 ** cur * factor
		while candidate <= N:
			if candidate not in used:
				used.add(candidate)
				ans += 1
				need -= cur
				if need <= 0:
					return ans
			factor += 1
			candidate = 2 ** cur * factor
		cur -= 1
	return -1
ReturnMode = True
t = 0
if not t:
	t = int(input())
for _ in range(t):
	ans = solve()
	if ReturnMode:
		print(ans) if type(ans) != list else print(*ans)


def solve():
	n = int(input())
	lis = list(map(int, input().split()))
	ans = 0
	for i in lis:
		while not i % 2:
			ans += 1
			i //= 2
	if ans >= n:
		print(0)
		return
	cnt = 0
	ref = list()
	for i in range(n + 1):
		cnt = int()
		while not i % 2 and i > 0:
			i //= 2
			cnt += 1
		ref.append(cnt)
	ref.sort(reverse=True)
	i = 0
	cnt = 0
	while i < len(ref) and ans < n:
		ans += ref[i]
		i += 1
		cnt += 1
	print(-1 if ans < n else cnt)
for _ in range(int(input())):
	solve()


import sys
from collections import *
sys.setrecursionlimit(10 ** 5)
itr = (line for line in sys.stdin.read().strip().split('\n'))
INP = lambda : next(itr)

def ni():
	return int(INP())

def nl():
	return [int(_) for _ in INP().split()]

def solve(n, a):
	e = 0
	d = {}
	for i in range(1, 32):
		d[2 ** i] = i
	div = list(d.keys())
	for i in a:
		if i % 2 == 0:
			best = 2
			for num in div:
				if i % num == 0:
					best = num
			e += d[best]
	if e >= n:
		print(0)
		return
	add = 0
	fa = []
	for i in range(n, 0, -1):
		if i % 2 == 0:
			best = 2
			for num in div:
				if i % num == 0:
					best = num
			fa.append(d[best])
	fa.sort(reverse=True)
	for i in fa:
		e += i
		add += 1
		if e >= n:
			print(add)
			return
	print(-1)
	return
t = ni()
for case in range(t):
	n = ni()
	a = nl()
	solve(n, a)


import math
import collections
import bisect
import heapq
from collections import deque
from math import sqrt, ceil, floor

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

def inp_str_arr():
	return list(input().strip().split(' '))

def inp_str():
	return input()

def cal_2s(n):
	cnt = 0
	while n % 2 == 0:
		cnt += 1
		n = n // 2
	return cnt

def solve():
	(n,) = inp_arr()
	a = inp_arr()
	cnt = 0
	for x in a:
		cnt += cal_2s(x)
	if cnt >= n:
		print(0)
		return
	lis = []
	for i in range(1, n + 1):
		lis.append(cal_2s(i))
	lis.sort(reverse=True)
	need = n - cnt
	ans = 0
	i = 0
	while need > 0 and i < n:
		ans += 1
		need = need - lis[i]
		i += 1
	if need > 0:
		print(-1)
		return
	print(ans)
(tt,) = inp_arr()
for t in range(tt):
	solve()


def factor(a):
	count = 0
	while a % 2 == 0:
		count += 1
		a = a // 2
	return count
t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	factor_sum = 0
	for i in range(n):
		factor_sum += factor(arr[i])
	diff = n - factor_sum
	if diff <= 0:
		print(0)
	else:
		factor_list = []
		for i in range(1, n + 1):
			factor_list.append(factor(i))
		factor_list.sort(reverse=True)
		count = 0
		start = 0
		while diff > 0:
			diff -= factor_list[start]
			count += 1
			start += 1
			if start == n and diff > 0:
				count = -1
				break
		print(count)


from sys import stdin

def cant_2(a):
	cont = 0
	for n in a:
		while n % 2 == 0:
			cont += 1
			n = n // 2
	return cont

def main():
	cases = int(stdin.readline().strip())
	for c in range(cases):
		n = int(stdin.readline().strip())
		a = list(map(int, stdin.readline().strip().split()))
		m = cant_2(a)
		if m >= n:
			print('0')
		elif n == 1:
			print('-1')
		else:
			if n % 2 == 0:
				k = n
			else:
				k = n - 1
			lista = [i for i in range(2, k + 1, 2)]
			pasos = []
			for l in lista:
				cont = 0
				while l % 2 == 0:
					cont += 1
					l = l // 2
				pasos += [cont]
			p = sorted(pasos)
			andando = 0
			flag = True
			while len(p) > 0 and flag:
				a = p.pop()
				m += a
				andando += 1
				if m >= n:
					print(str(andando))
					flag = False
			if flag:
				print('-1')
main()


t = int(input())

def timesDivisible(k):
	tot = 0
	while k % 2 == 0:
		tot += 1
		k //= 2
	return tot
for _ in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	twos = 0
	for i in range(n):
		twos += timesDivisible(a[i])
	if twos >= n:
		print(0)
	else:
		moves = 0
		q = []
		for i in range(n, 0, -1):
			if i % 2 == 0:
				q.append(timesDivisible(i))
		q.sort(reverse=True)
		for i in range(len(q)):
			twos += q[i]
			moves += 1
			if twos >= n:
				break
		if twos >= n:
			print(moves)
		else:
			print(-1)


def main():
	n_tests = int(input())
	for _ in range(n_tests):
		n = int(input())
		arr = list(map(int, input().split(' ')))
		twos = 0
		for elem in arr:
			t = 0
			e_init = elem
			while elem % 2 == 0:
				t += 1
				elem = elem // 2
			twos += t
		if twos >= n:
			print(0)
			continue
		idx = []
		for x in range(1, n + 1):
			e_init = elem
			x_init = x
			t = 0
			while elem % 2 == 0:
				t += 1
				elem = elem // 2
			while x % 2 == 0:
				t += 1
				x = x // 2
			idx.append((x_init, t))
		ops = 0
		for pair in reversed(sorted(idx, key=lambda x: x[1])):
			ops += 1
			twos += pair[1]
			if twos >= n:
				break
		if twos >= n:
			print(ops)
		else:
			print(-1)
main()


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

	def twos(p):
		count = 0
		while p % 2 == 0:
			count += 1
			p = p // 2
		return count
	num_of_twos = 0
	for i in lst:
		num_of_twos += twos(i)
	remain = n - num_of_twos
	if remain <= 0:
		print(0)
	else:
		count = 0
		array = []
		for i in range(2, n + 1):
			array.append(twos(i))
		array.sort(reverse=True)
		for i in array:
			if remain >= i:
				remain -= i
				count += 1
			if remain == 0:
				break
		if remain > 0:
			print(-1)
		else:
			print(count)


from collections import defaultdict, Counter, deque
import sys
import threading
from sys import stdin, stdout
sys.setrecursionlimit(1 << 30)
threading.stack_size(1 << 27)

def main():

	def count_two(num):
		count = 0
		while num and (not num % 2):
			count += 1
			num //= 2
		return count
	t = int(stdin.readline())
	for _ in range(t):
		n = int(stdin.readline())
		nums = list(map(int, stdin.readline().split()))
		have = []
		count = 0
		total = 0
		rem = 0
		for (idx, num) in enumerate(nums):
			twos = count_two(idx + 1)
			total += count_two(num)
			if twos:
				have.append(twos)
		if total:
			if total % n and total < n:
				rem = n - total
		else:
			rem = n
		have.sort()
		while rem and have:
			popped = have.pop()
			if popped <= rem:
				rem -= popped
				count += 1
		if rem:
			print(-1)
		else:
			print(count)
thread = threading.Thread(target=main)
thread.start()
thread.join()


def my_log(n):
	ans = 0
	while not n % 2:
		n //= 2
		ans += 1
	return ans
for _ in range(int(input())):
	(n, l) = (int(input()), list(map(int, input().split())))
	prod = 0
	for i in l:
		prod += my_log(i)
	ans = 0
	ind_logs = sorted(map(my_log, range(1, n + 1)), reverse=True)
	for i in ind_logs:
		if prod >= n:
			break
		prod += i
		ans += 1
	print(-1 if prod < n else ans)


def implementation(n, data):
	initial = 0
	for i in range(n):
		initial += find_power(data[i])
	if initial >= n:
		print(0)
		return
	adder = less(n)
	if adder == 0:
		print(-1)
		return
	compare = 2 ** adder
	multiplier = 1
	steps = 0
	while adder > 0 and initial < n:
		while compare * multiplier <= n and initial < n:
			initial += adder
			multiplier += 2
			steps += 1
		multiplier = 1
		adder -= 1
		compare = compare // 2
	if initial < n:
		print(-1)
	else:
		print(steps)

def find_power(num):
	power = 0
	while num % 2 == 0:
		power += 1
		num = num // 2
	return power

def less(num):
	answer = 0
	compare = 1
	while compare <= num:
		compare *= 2
		answer += 1
	return answer - 1
t = int(input())
for i in range(t):
	length = int(input())
	data = input().split(' ')
	for i in range(len(data)):
		data[i] = int(data[i])
	implementation(length, data)


from math import ceil

def count_two(x):
	ans = 0
	while x % 2 == 0:
		ans += 1
		x //= 2
	return ans

def count_bits(n):
	ans = 0
	while n > 0:
		n //= 2
		ans += 1
	return ans - 1
tc = int(input())
for _ in range(tc):
	n = int(input())
	a = [int(x) for x in input().split()]
	twos = 0
	for x in a:
		twos += count_two(x)
	if twos >= n:
		print(0)
	else:
		ans = 0
		b = count_bits(n)
		xops = 0
		while b > 0:
			ops = n // 2 ** b
			ops -= xops
			if twos + ops * b >= n:
				o = ceil((n - twos) / b)
				ans += o
				twos = n
				break
			else:
				twos += ops * b
				ans += ops
			b -= 1
			xops += ops
		if twos < n:
			print(-1)
		else:
			print(ans)


import math
t = int(input())

def power_2(x):
	count = 0
	while x % 2 == 0 and x > 0:
		x //= 2
		count += 1
	return count

def solve():
	n = int(input())
	arr = list(map(int, input().split()))
	initial_power = 0
	for num in arr:
		initial_power += power_2(num)
	if initial_power >= n:
		print(0)
	else:
		i = 2
		lst = []
		while i <= n:
			lst += [i]
			i += 2
		lst.sort(key=power_2, reverse=True)
		operations = 0
		for i in range(len(lst)):
			initial_power += power_2(lst[i])
			operations += 1
			if initial_power >= n:
				break
		if initial_power < n:
			print(-1)
		else:
			print(operations)
while t:
	solve()
	t -= 1


def counter(num):
	c = 0
	while num % 2 == 0:
		c += 1
		num //= 2
	return c
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	c = 0
	for num in a:
		c += counter(num)
	if c >= n:
		print(0)
	else:
		temp = []
		for i in range(2, n + 1, 2):
			temp.append(counter(i))
		temp.sort(reverse=True)
		j = 0
		while c < n and j < len(temp):
			c += temp[j]
			j += 1
		if c >= n:
			print(j)
		else:
			print(-1)


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

def solve():
	n = int(input())
	indeces = []
	twos = 0
	nums = input().split(' ')
	for i in range(1, n + 1):
		curr = int(nums[i - 1])
		twos += count_2_factors(curr)
		factors = count_2_factors(i)
		if factors > 0:
			indeces.append(factors)
	if twos >= n:
		return 0
	count = 0
	indeces.sort(reverse=True)
	for f in indeces:
		if twos >= n:
			break
		twos += f
		count += 1
	if twos >= n:
		return count
	return -1

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


def countTwos(n):
	two = 0
	while n % 2 == 0:
		n = n // 2
		two += 1
	return two
t = int(input())
while t > 0:
	n = int(input())
	arr = list(map(int, input().split()))
	twos = 0
	for i in range(n):
		twos += countTwos(arr[i])
	if twos >= n:
		print(0)
	else:
		cnt = 0
		flag = 0
		dic = {}
		for i in range(n, 0, -1):
			if i % 2 == 0:
				dic[i] = countTwos(i)
		dic = {k: v for (k, v) in sorted(dic.items(), key=lambda item: item[1], reverse=True)}
		for k in dic.keys():
			twos += dic[k]
			cnt += 1
			if twos >= n:
				flag = 1
				break
		if flag == 1:
			print(cnt)
		else:
			print(-1)
	t -= 1


t = int(input())

def numtwos(n):
	twos = 0
	while n % 2 == 0:
		twos += 1
		n = n // 2
	return twos

def genarr(n):
	res = []
	for i in range(17, 0, -1):
		l = (n // (1 << i) - 1) // 2
		if l >= 0:
			res.extend([i] * (l + 1))
	return res + [0] * max(n - len(res), 0)
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	x = 1 << n
	twos = 0
	for el in arr:
		twos += numtwos(el)
	if twos >= n:
		print(0)
	else:
		diff = n - twos
		twos = genarr(n)
		i = 0
		while diff > 0 and i < n:
			diff -= twos[i]
			i += 1
		print(i if i < n else -1)


def d(x):
	cnt = 0
	while x % 2 == 0:
		cnt += 1
		x = x // 2
	return cnt
for _ in range(int(input())):
	k = int(input())
	li = list(map(int, input().split()))
	if 0 in li:
		print(-1)
		continue
	i = 0
	for x in li:
		i += d(x)
	if i >= k:
		print(0)
	elif i == 0:
		print(-1)
	else:
		remaining = k - i
		if len(li) % 2 == 0:
			longEven = len(li)
		else:
			longEven = len(li) - 1
		king = []
		for i in range(1, longEven + 1):
			if i % 2 == 0:
				n = i
				temp = d(n)
				king.append(temp)
		king.sort(reverse=True)
		ops = 0
		mm = 0
		while len(king) != mm:
			xx = king[mm]
			remaining -= xx
			ops += 1
			if remaining <= 0:
				break
			mm += 1
		if remaining > 0:
			print(-1)
			continue
		print(ops)


t = int(input())

def d(x):
	res = 0
	while x % 2 == 0:
		res += 1
		x //= 2
	return res
while t:
	t -= 1
	n = int(input())
	a = [*map(int, input().split())]
	s = 0
	k = []
	for i in range(n):
		tmp = a[i]
		s += d(tmp)
		k.append(d(i + 1))
	k.sort(reverse=True)
	i = 0
	while i < n and s < n:
		s += k[i]
		i += 1
	if s >= n:
		print(i)
	else:
		print(-1)


def ii():
	i = input().split()
	try:
		if len(i) == 1:
			return int(i[0])
		return list(map(int, i))
	except Exception:
		if len(i) == 1:
			return i[0]
		return i

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)

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

def ceil(n):
	if n % 1 == 0:
		return int(n)
	else:
		return int(n) + 1
for _ in range(ii()):
	n = ii()
	no = n
	a = ii()
	if isinstance(a, int):
		a = [a]
	r = 0
	result = 0
	for i in a:
		r += check(i)
	l = []
	s = 0
	while n > 1:
		n //= 2
		if len(l):
			l[len(l) - 1] -= n
		l.append(n)
		s += n
	if s + r < no:
		print('-1')
		continue
	if r >= no:
		print('0')
		continue
	for (i, v) in reversed(list(enumerate(l))):
		t = (no - r) / (i + 1)
		if t <= v:
			result += ceil(t)
			print(result)
			break
		else:
			result += v
			r += (i + 1) * v


def opt(x):
	kol = 0
	while x % 2 == 0:
		kol += 1
		x //= 2
	return kol
for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ans = 0
	num_list = []
	for i in range(n):
		ans += opt(a[i])
		num_list.append(opt(i + 1))
	num_list.sort(reverse=True)
	ind = 0
	while ind < n and ans < n:
		ans += num_list[ind]
		ind += 1
	if ans >= n:
		print(ind)
	else:
		print(-1)


import os
import math
import collections
import bisect
import functools
import itertools
import heapq

def solve(a, n):
	count = 0
	for x in a:
		v = x
		while v % 2 == 0:
			count += 1
			v //= 2
	if count >= n:
		return 0
	d = n - count
	m = int(math.log2(n))
	ans = 0
	pre = 0
	while d > 0 and m > 0:
		x = 2 ** m
		y = n // x - pre
		if m * y < d:
			d -= m * y
			ans += y
			pre += y
			m -= 1
		else:
			ans += int(math.ceil(d / m))
			d = 0
	return ans if d <= 0 else -1
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	print(solve(a, n))


def d(x):
	ak = 0
	while x % 2 == 0:
		ak += 1
		x //= 2
	return ak
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split(' ')))
	s = 0
	k = []
	for i in range(n):
		s += d(a[i])
		k.append(d(i + 1))
	k.sort(reverse=True)
	j = 0
	while s < n and j < n:
		s += k[j]
		j += 1
	if s >= n:
		print(j)
	else:
		print(-1)


def st(n):
	p = 2
	count = 0
	while n % p == 0:
		count += 1
		n = n // p
	return count
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	count = 0
	b = []
	for j in range(n):
		count += st(a[j])
		b.append(st(j + 1))
	if count < n:
		b.sort(reverse=True)
		d = 0
		l = 0
		while count < n and b[l] != 0:
			count += b[l]
			l += 1
			d += 1
		if count >= n:
			print(d)
		else:
			print(-1)
	else:
		print(0)


def re(x):
	di = 0
	while x % 2 == 0:
		di += 1
		x //= 2
	return di
for i in range(int(input())):
	sum = 0
	index = []
	n = int(input())
	lst = list(map(int, input().split()))
	for one in range(n):
		sum += re(lst[one])
		index.append(re(one + 1))
	index.sort(reverse=True)
	i = 0
	while i < n:
		if sum >= n:
			print(i)
			break
		else:
			sum += index[i]
			i += 1
	else:
		print(-1)


import math
power = [0] * 200001
for i in range(2, 200001):
	if i % 2 != 0:
		power[i] = 0
	else:
		power[i] = 1 + power[i // 2]

def func(x):
	ans = 0
	while x % 2 == 0:
		ans += 1
		x = x // 2
	return ans
from collections import defaultdict
t = int(input())
for _ in range(t):
	n = int(input())
	arr = []
	p = 0
	for x in input().split():
		arr.append(int(x))
		p += func(int(x))
	ans = 0
	if p >= n:
		ans = 0
		diff = 0
	else:
		diff = n - p
		bla = sorted(power[1:n + 1], reverse=True)
		for f in range(n):
			diff -= bla[f]
			ans += 1
			if diff <= 0:
				break
	if diff > 0:
		ans = -1
	print(ans)


t = int(input())

def pow2(x):
	ans = 0
	while x % 2 == 0:
		ans += 1
		x //= 2
	return ans
while t > 0:
	n = int(input())
	arr = list(map(int, input().split()))
	cp = 0
	for val in arr:
		cp += pow2(val)
	powers = []
	for i in range(1, n + 1):
		powers.append(pow2(i))
	need = n - cp
	moves = 0
	i = 0
	powers.sort(reverse=True)
	while i < len(powers) and need > 0:
		need -= powers[i]
		moves += 1
		i += 1
	if need <= 0:
		print(moves)
	else:
		print(-1)
	t -= 1


def countPow2(k):
	count = 0
	while k % 2 == 0:
		count += 1
		k //= 2
	return count
for _ in [0] * int(input()):
	n = int(input())
	nums = list(map(int, input().rstrip().split()))
	total = extra = 0
	extArr = []
	for num in nums:
		total += countPow2(num)
	for i in range(2, n + 1):
		temp = countPow2(i)
		extra += temp
		extArr += [temp]
	extArr.sort(reverse=True)
	if total >= n:
		print(0)
	elif total + extra < n:
		print(-1)
	else:
		ans = 0
		for i in range(len(extArr)):
			ans += 1
			if total + extArr[i] >= n:
				break
			total += extArr[i]
		print(ans)


def getTwo(n):
	count = 0
	while n % 2 == 0:
		count += 1
		n //= 2
	return count
for _ in range(int(input())):
	n = int(input())
	nums = list(map(int, input().split()))
	ans = 0
	counts = []
	op = 0
	for i in range(len(nums)):
		ans += getTwo(nums[i])
		counts.append(getTwo(i + 1))
	counts.sort()
	for i in range(len(counts) - 1, -1, -1):
		if ans < len(nums):
			if counts[i] > 0:
				ans += counts[i]
				op += 1
			else:
				break
		else:
			break
	if ans >= len(nums):
		print(op)
	else:
		print(-1)


def get_pwr2(v):
	res = 0
	while v % 2 == 0:
		res += 1
		v //= 2
	return res

def solve(a, n):
	pwr2 = 0
	pwr2_add = [0] * n
	for ni in range(n):
		pwr2 += get_pwr2(a[ni])
		pwr2_add[ni] = get_pwr2(ni + 1)
	pwr2_add.sort(reverse=True)
	ns = 0
	while pwr2 < n:
		if pwr2_add[ns] == 0:
			break
		pwr2 += pwr2_add[ns]
		ns = ns + 1
	if pwr2 < n:
		return -1
	return ns
t = int(input())
ans = []
for ti in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	ans.append(solve(a, n))
for a in ans:
	print(a)


def count_two(num):
	count = 0
	while num % 2 == 0:
		count += 1
		num //= 2
	return count
test = int(input())
for _ in range(test):
	n = int(input())
	nums = list(map(int, input().split()))
	s = 0
	arr = []
	for i in range(n):
		s += count_two(nums[i])
		arr.append(count_two(i + 1))
	arr.sort(reverse=True)
	count = 0
	while s < n and count < n:
		s += arr[count]
		count += 1
	if s >= n:
		print(count)
	else:
		print(-1)


import sys
input = sys.stdin.readline
t = int(input())

def countTwos(num):
	count = 0
	while num % 2 == 0:
		count += 1
		num = num / 2
	return count
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	currentTwos = 0
	for num in a:
		currentTwos += countTwos(num)
	availbleTwos = []
	sumOfAvailbleTwos = 0
	for i in range(2, n + 1, 2):
		twos = countTwos(i)
		availbleTwos.append(twos)
	availbleTwos.sort(reverse=True)
	if currentTwos >= n:
		print(0)
	else:
		operations = 0
		for num in availbleTwos:
			if currentTwos >= n:
				break
			currentTwos += num
			operations += 1
		if currentTwos >= n:
			print(operations)
		else:
			print(-1)


t = int(input())

def c(n):
	co = 0
	while n % 2 == 0:
		n //= 2
		co += 1
	return co
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	count = 0
	ar = [0] * n
	ct = 0
	for i in range(n):
		ar[i] = c(i + 1)
		count += c(a[i])
	ar.sort()
	need_count = n - count
	if need_count <= 0:
		print(0)
	else:
		cou = 0
		i = n - 1
		for i in range(n - 1, -1, -1):
			if need_count <= 0:
				break
			elif ar[i] <= need_count:
				cou += 1
				need_count -= ar[i]
		if need_count > 0:
			print(-1)
		else:
			print(cou)


from math import *

def st2(x):
	k = 0
	while x % 2 == 0:
		x //= 2
		k += 1
	return k
t = int(input())
di = {x: 2 ** x for x in range(1, 31)}
for pupu in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	re = n
	cur = 0
	for i in a:
		if i % 2 == 0:
			cur += st2(i)
	sp = []
	for i in range(1, n + 1):
		if i % 2 == 0:
			sp.append(st2(i))
	sp = sorted(sp)[::-1]
	if n <= cur:
		print(0)
	else:
		an = 0
		for i in range(len(sp)):
			cur += sp[i]
			if cur >= n:
				an = i + 1
				break
		if an:
			print(an)
		else:
			print(-1)


def power2(x):
	pow = 0
	while x % 2 == 0:
		pow += 1
		x /= 2
	return pow

def maxmultiple2(n):
	max = 2
	while max <= n:
		max *= 2
	return max // 2
import math

def sol():
	n = int(input())
	a = [int(i) for i in input().split()]
	pow = 0
	for i in range(n):
		pow += power2(a[i])
	if n == 1 and a[0] % 2 != 0:
		print(-1)
	elif pow >= n:
		print(0)
	else:
		vis = []
		n2 = n
		ans = 0
		for i in range(n):
			vis.append(power2(i + 1))
		vis.sort(reverse=True)
		for i in range(n):
			pow += vis[i]
			if pow >= n:
				ans += i + 1
				break
		if pow >= n:
			print(ans)
		else:
			print(-1)
t = int(input())
for i in range(t):
	sol()


def get_count_2(num):
	count = 0
	while num % 2 == 0:
		num /= 2
		count += 1
	return count
for _ in range(int(input())):
	length = int(input())
	array = map(int, input().split())
	count_2 = sum(map(get_count_2, filter(lambda x: x % 2 == 0, array)))
	i = length - 1 * (length % 2)
	step = 0
	if length <= count_2:
		print(step)
		continue
	for i in sorted(map(get_count_2, [i for i in range(2, length + 1, 2)]), reverse=True):
		count_2 += i
		step += 1
		if length <= count_2:
			break
	else:
		print(-1)
		continue
	print(step)


from sys import *
input = stdin.readline
t = int(input())

def ctz(x):
	s = 0
	while x % 2 == 0:
		s += 1
		x /= 2
	return s
while t > 0:
	t -= 1
	n = int(input())
	a = sum([ctz(int(x)) for x in input().split()])
	b = [ctz(i + 1) for i in range(n)]
	b.sort()
	b.reverse()
	steps = 0
	for i in range(n):
		if a >= n:
			break
		a += b[i]
		steps += 1
	if a >= n:
		print(steps)
	else:
		print(-1)


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 countZeros(num):
	length = num.bit_length()
	result = 0
	for i in range(length):
		if num & 1 << i:
			break
		result += 1
	return result

def main():
	for _ in range(inp()):
		n = inp()
		nums = inlt()
		indexZeros = []
		currentZeros = 0
		for (i, num) in enumerate(nums):
			indexZeros.append(countZeros(i + 1))
			currentZeros += countZeros(num)
		if currentZeros >= n:
			print(0)
		else:
			indexZeros.sort(reverse=True)
			count = 0
			found = False
			for i in range(len(indexZeros)):
				currentZeros += indexZeros[i]
				if currentZeros >= n:
					print(i + 1)
					found = True
					break
			if not found:
				print(-1)
main()


def count(i):
	if i == 0:
		return 0
	c = 0
	while i % 2 == 0:
		i //= 2
		c += 1
	return c
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(i) for i in input().split()]
	total = 0
	add = []
	for i in range(len(a)):
		total += count(a[i])
		x = count(i + 1)
		if x != 0:
			add.append(x)
	i = len(add) - 1
	ops = 0
	add = sorted(add)
	while i >= 0 and total < n:
		total += add[i]
		i -= 1
		ops += 1
	if total >= n:
		print(ops)
	else:
		print(-1)


def twoFact(n):
	ans = 0
	while n != 0:
		if not n & 1:
			ans += 1
			n //= 2
		else:
			break
	return ans
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	tot = 0
	for i in range(n):
		tot += twoFact(arr[i])
	if tot >= n:
		print(0)
	else:
		ops = 0
		done = False
		twoList = []
		for i in range(1, n + 1):
			twoList.append(twoFact(i))
		twoList = sorted(twoList, reverse=True)
		for add in twoList:
			tot += add
			ops += 1
			if tot >= n:
				done = True
				break
		if done:
			print(ops)
		else:
			print(-1)


def div_2_count(x):
	cnt = 0
	while x % 2 == 0:
		cnt += 1
		x //= 2
	return cnt
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	total_div2_cnt = 0
	for i in range(n):
		total_div2_cnt += div_2_count(a[i])
	indx_div_2_count_list = []
	for i in range(1, n + 1):
		indx_div_2_count_list.append(div_2_count(i))
	indx_div_2_count_list.sort(reverse=True)
	i = 0
	while i < n and total_div2_cnt < n:
		total_div2_cnt += indx_div_2_count_list[i]
		i += 1
	if total_div2_cnt >= n:
		print(i)
	else:
		print(-1)


def find_divisibility_by_2_power_n(arr, n):
	even_count = 0
	arr2 = []
	for (x, i) in enumerate(arr):
		while i % 2 == 0:
			i = i // 2
			even_count += 1
		idx = x + 1
		count = 0
		while idx % 2 == 0:
			idx = idx // 2
			count += 1
		arr2.append(count)
	arr2.sort()
	arr2.reverse()
	if even_count >= n:
		return 0
	for (x, i) in enumerate(arr2):
		even_count += i
		if even_count >= n:
			return x + 1
	if even_count < n:
		return -1
num_cases = int(input())
for i in range(num_cases):
	n = int(input())
	arr = [int(j) for j in input().split()]
	print(find_divisibility_by_2_power_n(arr, n))


def number_of_2(x):
	n = 0
	while x > 0 and x % 2 == 0:
		x //= 2
		n += 1
	return n

def solve():
	n = int(input())
	a = map(int, input().split())
	k = 0
	for e in a:
		k += number_of_2(e)
	h = []
	for i in range(2, n + 1, 2):
		h.append(number_of_2(i))
	h = sorted(h, reverse=True)
	if k >= n:
		print('0')
		return
	ans = 0
	for i in h:
		k += i
		ans += 1
		if k >= n:
			break
	print(-1 if k < n else ans)
for _ in range(int(input())):
	solve()


inp = []
for _ in range(int(input())):
	input()
	inp.append([int(x) for x in input().split(' ')])

def fac(x):
	c = 0
	while x % 2 == 0:
		x /= 2
		c += 1
	return c
for arr in inp:
	t = 0
	res = []
	for (e, n) in enumerate(arr):
		t += fac(n)
		x = fac(e + 1)
		if x:
			res.append(x)
	res.sort(reverse=True)
	l = len(arr)
	if t >= l:
		print(0)
		continue
	for (e, f) in enumerate(res):
		t += f
		if t >= l:
			break
	if t >= l:
		print(e + 1)
	else:
		print(-1)


def bi(n):
	c1 = 0
	while n % 2 != 1:
		n = n / 2
		c1 = c1 + 1
	return c1
s = int(input())
for i in range(0, s):
	a = int(input())
	n = list(map(int, input().split()))
	c2 = 0
	for k in range(0, len(n)):
		c2 = c2 + bi(n[k])
	if c2 >= a:
		print(0)
	else:
		r1 = []
		for k in range(1, a + 1):
			r1.append(bi(k))
		r1.sort(reverse=True)
		c = 0
		for j in range(0, len(r1)):
			if c2 + r1[j] < a:
				c = c + 1
				c2 = c2 + r1[j]
			else:
				c2 = c2 + r1[j]
				c = c + 1
				break
		if c2 < a:
			print(-1)
		else:
			print(c)


def f(arr, n):
	exp = 0
	values = []
	for (i, el) in enumerate(arr):
		k = el
		while k % 2 == 0:
			exp += 1
			k //= 2
		k = i + 1
		count = 0
		while k % 2 == 0:
			count += 1
			k //= 2
		values.append(count)
	values.sort()
	operations_count = 0
	while exp < n and len(values) > 0:
		v = values.pop()
		exp += v
		operations_count += 1
	if exp >= n:
		return operations_count
	return -1
t = int(input())
for i in range(t):
	n = int(input())
	arr = [int(el) for el in input().split(' ')]
	print(f(arr, n))


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 solve(n, arr):
	sum_two_count = 0
	for (i, j) in enumerate(arr):
		while j % 2 == 0:
			j /= 2
			sum_two_count += 1
	if sum_two_count >= n:
		return 0
	twos_need = n - sum_two_count
	twos_available = []
	for j in range(n, 0, -1):
		t = 0
		while j % 2 == 0:
			j /= 2
			t += 1
		twos_available.append(t)
	twos_available.sort(reverse=True)
	operations = 0
	for i in twos_available:
		if twos_need <= 0:
			return operations
		twos_need -= i
		operations += 1
	return -1
for _ in range(inp()):
	n = inp()
	print(solve(n, inlt()))


def solve(n):
	if n % 2:
		return 0
	res = 0
	while n % 2 == 0:
		res += 1
		n = n // 2
	return res
t = int(input())
while t:
	n = int(input())
	a = [int(i) for i in input().split()]
	p = 0
	for i in range(n):
		p += solve(a[i])
	k = n - p
	d = []
	for i in range(1, n + 1):
		d.append(solve(i))
	d.sort(reverse=True)
	res = 0
	i = 0
	while k > 0 and i < n:
		k -= d[i]
		res += 1
		i += 1
	if k > 0:
		print('-1')
	else:
		print(res)
	t -= 1


def solve(A, N, s):
	v = []
	c = 0
	for i in range(N, 0, -1):
		c = 0
		if i % 2 == 0:
			while i % 2 == 0:
				c += 1
				i /= 2
			v.append(c)
	v.sort()
	for (i, e) in enumerate(reversed(v)):
		s += e
		if s >= N:
			return i + 1
	return -1

def main():
	for _ in range(int(input())):
		N = int(input())
		A = []
		s = 0
		for e in list(map(int, input().split())):
			while e % 2 == 0:
				e /= 2
				s += 1
			A.append(e)
		if s >= N:
			print(0)
		else:
			print(solve(A, N, s))
main()


def func():
	n = int(input())
	w = list(map(int, input().split()))
	div = 0
	for i in range(n):
		x = w[i]
		while x % 2 == 0:
			x /= 2
			div += 1
	if div >= n:
		return 0
	else:
		v = []
		for i in range(n):
			r = 0
			a = i + 1
			while a % 2 == 0:
				r += 1
				a /= 2
			v.append(r)
		v.sort(reverse=True)
		res = 0
		i = 0
		while div < n and i < n:
			div += v[i]
			res += 1
			i += 1
		if div >= n:
			return res
		else:
			return -1
t = int(input())
for i in range(t):
	ans = func()
	print(ans)


def numd(n):
	a = 0
	while n % 2 == 0:
		a += 1
		n /= 2
	return a
t = int(input())
for i in range(t):
	n = int(input())
	st = input()
	arr = [int(i) for i in st.split()]
	res = 0
	n = len(arr)
	n_1 = 0
	rarr = sorted([numd(i) for i in range(1, len(arr) + 1)], reverse=True)
	for i in arr:
		n_1 += numd(i)
	if n <= n_1:
		print(0)
	else:
		for i in rarr:
			if i != 0:
				n_1 += i
				res += 1
			if n_1 >= n:
				break
		if n_1 < n:
			print(-1)
		else:
			print(res)


def l(x):
	ans = 0
	while x % 2 == 0:
		ans += 1
		x //= 2
	return ans
for i in range(int(input())):
	d2 = [0] * 20
	n = int(input())
	a = list(map(int, input().split()))
	ans = 0
	ansd = 0
	for i in range(n):
		ans += l(a[i])
		buff = l(i + 1)
		d2[buff] += 1
		ansd += buff
	d2[0] = 0
	if ans + ansd >= n:
		j = 19
		co = 0
		while ans < n:
			if d2[j] * j + ans >= n:
				co += (n - ans) // j + ((n - ans) % j > 0)
				break
			else:
				co += d2[j]
				ans += d2[j] * j
			j -= 1
		print(co)
	else:
		print(-1)


def find_max(num):
	cur = 0
	while num > 1:
		if num % 2 == 0:
			num //= 2
			cur += 1
		else:
			break
	return cur
for t in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	raw = 0
	for i in lst:
		raw += find_max(i)
	if raw >= n:
		print('0')
	else:
		cnt = 0
		c = raw
		done = False
		l = []
		for j in list(range(2, n + 1, 2))[::-1]:
			l.append(find_max(j))
		for j in sorted(l, reverse=True):
			c += j
			cnt += 1
			if c >= n:
				done = True
				break
		if not done:
			print('-1')
		else:
			print(f'{cnt}')


def power_of_two(num):
	count = 0
	while num % 2 == 0:
		num /= 2
		count += 1
	return count
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	arr1 = []
	for i in range(1, n + 1):
		arr1.append(power_of_two(i))
	arr1.sort(reverse=True)
	two = []
	for item in arr:
		two.append(power_of_two(item))
	s = sum(two)
	s1 = sum(arr1)
	if s + s1 < n:
		print(-1)
	elif s >= n:
		print(0)
	else:
		dif = n - s
		count = 0
		for item in arr1:
			dif -= item
			count += 1
			if dif <= 0:
				break
		print(count)


from math import log2

def solve():
	n = int(input())
	nums = [int(x) for x in input().split()]
	twos = 0
	for num in nums:
		while num % 2 == 0:
			twos += 1
			num //= 2
	l = []
	for i in range(1, n + 1):
		x = 0
		while i % 2 == 0:
			x += 1
			i //= 2
		l.append(x)
	l.sort()
	opers = 0
	while twos < n and l:
		twos += l.pop()
		opers += 1
	if twos >= n:
		print(opers)
	else:
		print(-1)
t = int(input())
for _ in range(t):
	solve()


import sys
import threading
from functools import lru_cache
from bisect import bisect_left
from collections import defaultdict, deque

def main():
	t = int(input())
	for _ in range(t):
		n = int(input())
		a = [int(i) for i in input().split()]
		possiblilies = [0] * n
		cnt = 0
		for index in range(n):
			num = a[index]
			while num % 2 == 0:
				num //= 2
				cnt += 1
			cur = index + 1
			while cur % 2 == 0:
				cur //= 2
				possiblilies[index] += 1
		req = n - cnt
		if req <= 0:
			print(0)
			continue
		possiblilies.sort(reverse=True)
		ans = 0
		for pos in possiblilies:
			if pos >= req:
				req = 0
				ans += 1
				break
			else:
				req -= pos
				ans += 1
		if not req:
			print(ans)
		else:
			print(-1)
sys.setrecursionlimit(1 << 30)
threading.stack_size(1 << 27)
main_thread = threading.Thread(target=main)
main_thread.start()
main_thread.join()