You are given an array A of length N.

You can perform the following operation on the array any number of times:

Choose any [subsequence] S of the array A and a positive integer X such that X is a power of 2 and subtract X from all the elements of the subsequence S.

Find the minimum number of operations required to make all the elements of the array equal to 0.

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

- First line will contain T, number of test cases. Then the test cases follow.
- First line of each test case contains an integer N denoting the length of the array A.
- Second line contains N space-separated integers A_{1}, A_{2}, \ldots, A_{N} - denoting the elements of array A.

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

For each test case, output in a single line, the minimum number of moves required to make all the elements of the array A equal to 0.

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

$1 ≤ T ≤ 1000$
$1 ≤ N ≤ 10^{5}$
$0 ≤ A_{i} ≤ 10^{9}$
- Sum of $N$ over all test cases do not exceed $2 \cdot 10^{5}$.

----- Sample Input 1 ------ 
4
3
2 2 2
4
2 2 2 4
2
0 0
3
1 2 3

----- Sample Output 1 ------ 
1
2
0
2

----- explanation 1 ------ 
Test Case $1$: Take the subsequence with indices $\{1,2,3\}$ and subtract $2^{1} = 2$ from each element.

Test Case $2$: Take the subsequence with indices $\{1,2,3,4\}$ and subtract $2^{1} = 2$ from each element. After this operation, the array becomes $[0,0,0,2]$. Now, take the subsequence with index $\{4\}$ and subtract $2^{1} = 2$ from it.

Test Case $3$: All the elements are already $0$.

Test Case $4$: Take the subsequence with indices $\{2,3\}$ and subtract $2^{1}=2$ from it. Now, the array becomes $[1, 0, 1]$. Now, take the subsequence with indices $\{1, 3\}$ and subtract $2^{0}=1$ from it.

Difficulty: EASY
Tags: Bit manipulation

Mathematics

Greedy algorithms
Skill types: Bit manipulation

Greedy algorithms

Starter code:

Solutions:
g = int(input())

def algo():
	H = int(input())
	A = list(map(int, input().split()[:H]))
	o = 0
	for x in A:
		o = o | x
	c = 0
	for i in bin(o)[2:]:
		if i == '1':
			c += 1
	print(c)
for i in range(g):
	algo()


t = int(input())
for ni in range(t):
	n = int(input())
	l = [int(i) for i in input().split()]
	count = 0
	for i in l:
		count = count | i
	count = bin(count)[2:]
	print(count.count('1'))


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	s = 0
	for i in a:
		s = s | i
	s = bin(s)[2:]
	print(s.count('1'))


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	s = 0
	for i in l:
		s = s | i
	print(bin(s)[2:].count('1'))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	x = 0
	for i in a:
		x |= i
	print(bin(x).count('1'))


import math
for tc in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	(suba, temp) = (0, 0)
	cnt = 0
	while sum(a) > 0:
		cnt += 1
		if max(a) > 0:
			temp = int(math.log2(max(a)))
			suba = 2 ** temp
		for i in range(n):
			if a[i] >= suba:
				a[i] = a[i] - suba
	print(cnt)


for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	res = 0
	num = 0
	for a in A:
		num = num | a
	while num != 0:
		res += num & 1
		num >>= 1
	print(res)


testcase = int(input())
for i in range(testcase):
	n = int(input())
	arr = list(map(int, input().split()))
	aa = 0
	for nn in arr:
		aa = aa | nn
	print(bin(aa).count('1'))


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	f = 0
	for j in arr:
		f = f | j
	print(bin(f).count('1'))


T = int(input())
for i in range(T):
	N = int(input())
	f = 0
	l = list(map(int, input().split()))
	for j in l:
		f = f | j
	print(bin(f).count('1'))


for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	x = max(a)
	c = 0
	for i in a:
		c = c | i
	s = str(bin(c))
	k = 0
	for i in s:
		if i == '1':
			k += 1
	print(k)


for _ in range(int(input())):
	a = int(input())
	l = list(map(int, input().split()))
	c = 0
	for i in l:
		c = c | i
	k = 0
	c = bin(c)
	for i in range(len(c)):
		if c[i] == '1':
			k += 1
	print(k)


for i in range(int(input())):
	a = int(input())
	arr = list(map(int, input().split()))
	s = 0
	for j in arr:
		s |= j
	print(format(s, 'b').count('1'))


def mi(x, y2):
	if x >= y2:
		return mi(x, y2 * 2)
	else:
		return y2 // 2
t = int(input(''))
if 1 <= t <= 1000:
	for z in range(t):
		sum = 0
		n = int(input(''))
		a = map(int, input().split())
		a = list(a)
		while max(a) != 0:
			m = max(a)
			s = mi(m, 1)
			for i in range(n):
				if a[i] >= s:
					a[i] -= s
			sum += 1
		print(sum)


import math
for _ in range(int(input())):
	n = int(input())
	c = 0
	l = list(map(int, input().split()))
	for j in l:
		c = c | j
	print(bin(c).count('1'))


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	s = 0
	for i in l:
		s |= i
	print(format(s, 'b').count('1'))


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	c = 0
	for i in range(31, -1, -1):
		temp = 0
		for x in range(n):
			if a[x] - 2 ** i >= 0:
				a[x] -= 2 ** i
				temp += 1
		if temp:
			c += 1
	print(c)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = [int(x) for x in input().split()]
	f = 0
	for ele in arr:
		f = f | ele
	print(bin(f).count('1'))


t = input()
for c in range(0, int(t)):
	n = int(input())
	l = list(map(int, input().split()))
	bits = [0] * 30
	for i in range(n):
		for j in range(30):
			if 1 << j & l[i]:
				bits[j] += 1
	ans = 0
	for i in bits:
		if i > 0:
			ans += 1
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	a = tuple(map(int, input().split()))
	b = 0
	for i in range(n):
		b |= a[i]
	print(bin(b).count('1'))


import math
tests = int(input())
for i in range(tests):
	length = int(input())
	arr = list(set(map(int, input().split())))
	ans_arr = [0] * 32
	for x in arr:
		y = 0
		while x > 0:
			if x & 1:
				ans_arr[y] = 1
			y += 1
			x >>= 1
	print(ans_arr.count(1))


T = int(input())

def algo():
	N = int(input())
	A = list(map(int, input().split()[:N]))
	o = 0
	for x in A:
		o = o | x
	c = 0
	for i in bin(o)[2:]:
		if i == '1':
			c += 1
	print(c)
for i in range(T):
	algo()


for _ in range(int(input())):
	n = int(input())
	int_list = list(map(int, input().split()))
	ans = 0
	for i in int_list:
		ans = ans | i
	count = 0
	while ans:
		if ans & 1:
			count += 1
		ans >>= 1
	print(count)


import math
for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split(' ')))
	cnt = [0] * 32
	for i in range(n):
		for j in range(1, 32):
			if a[i] & 1 << j - 1:
				if cnt[j] == 0:
					cnt[j] = 1
					continue
	ans = 0
	for i in range(32):
		if cnt[i] != 0:
			ans += 1
	print(ans)


list_x = [2 ** x for x in range(32, -1, -1)]
t = int(input())
while t > 0:
	n = int(input())
	arr = [int(x) for x in input().split(' ')]
	cnt = 0
	ans = 0
	for x in arr:
		if x == 0:
			cnt += 1
	if cnt < n:
		for p in list_x:
			prev_arr = arr.copy()
			for (i, x) in enumerate(arr):
				if arr[i] - p >= 0:
					arr[i] = arr[i] - p
			cnt = 0
			for x in arr:
				if x == 0:
					cnt += 1
			if arr != prev_arr:
				ans += 1
			if cnt == n:
				break
	print(ans)
	t = t - 1


import math
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	c = 0
	while len(arr) != 0:
		try:
			ma = int(math.log(max(arr), 2))
		except:
			break
		ar = []
		for i in arr:
			if i >= 2 ** ma:
				if i - 2 ** ma != 0:
					ar.append(i - 2 ** ma)
			else:
				ar.append(i)
		arr = ar[:]
		c += 1
	print(c)


import math

def factors(n):
	arr = []
	while n != 0:
		factor = math.floor(math.log(n, 2))
		n -= math.pow(2, factor)
		arr.append(factor)
	return arr
for _ in range(int(input())):
	n = int(input())
	ip = list(map(int, input().split()))
	res = set()
	for i in ip:
		fact = factors(i)
		res.update(fact)
	print(len(res))


import sys
import math
from sys import stdin, stdout
import heapq

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

def get_int():
	return int(input())

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

def get_list_of_list(n):
	return [list(map(int, sys.stdin.readline().strip().split())) for _ in range(n)]

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

def main():
	for _ in range(get_int()):
		n = int(input())
		arr = [-v for v in get_ints_in_list()]
		if arr.count(0) == n:
			print(0)
			continue
		heapq.heapify(arr)
		ans = 1
		mxX = 1
		while mxX < abs(arr[0]):
			mxX *= 2
		if mxX > abs(arr[0]):
			mxX = mxX // 2
		f = 0
		while abs(arr[0]) != 0:
			if abs(arr[0]) < mxX:
				mxX = mxX // 2
				if f == 0:
					ans += 1
					f = 1
			else:
				f = 0
				el = abs(heapq.heappop(arr))
				heapq.heappush(arr, -1 * (el - mxX))
		print(ans)
main()


import math

def getFactors(n):
	factors = []
	while n != 0:
		fact = math.floor(math.log(n, 2))
		n = n - int(math.pow(2, fact))
		factors.append(fact)
	return factors
t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	s = set()
	for x in arr:
		factors = getFactors(x)
		s.update(factors)
	print(len(s))


import math

def getFactors(num):
	factors = []
	while num != 0:
		power = int(math.log(num, 2))
		factors.append(power)
		num -= math.pow(2, power)
	return factors
t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	powers = set()
	for n in arr:
		factors = getFactors(n)
		powers.update(factors)
	print(len(powers))


t = int(input())
j = 0
while j != t:
	n = int(input())
	a = list(map(int, input().split()))
	d = {}
	count = 0
	for i in range(n):
		for k in range(30):
			if 2 ** k & a[i] == 2 ** k:
				if 2 ** k in d.keys():
					d[2 ** k] += 1
				else:
					d[2 ** k] = 1
	for x in d:
		count += 1
	print(len(d))
	j += 1


powersOf2 = []
for iter in range(50):
	powersOf2.append(2 ** (iter + 1))
noOfTestCases = int(input())
for _ in range(noOfTestCases):
	N = int(input())
	Ais = list(set(map(int, input().split())))
	binary = 0
	for iter in range(len(Ais)):
		binary |= Ais[iter]
	print(bin(binary)[2:].count('1'))


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	v = 0
	for i in arr:
		v |= i
	ans = 0
	for j in bin(v)[2:]:
		if j == '1':
			ans += 1
	print(ans)


for _ in range(int(input())):
	n = int(input())
	arr = sorted(set(map(int, input().split())), reverse=True)
	ans = 0
	if len(arr) == 1:
		if arr[0] != 0:
			for i in bin(arr[0])[2:]:
				if i == '1':
					ans += 1
	else:
		binary = bin(arr[0])[2:][::-1]
		d = {i: int(binary[i]) for i in range(len(binary))}
		firstlen = len(d.keys())
		l = list(d.keys()).copy()
		for i in l:
			if d[i] == 1:
				d.pop(i)
		for i in range(1, len(arr)):
			binary = '{0:b}'.format(arr[i])[::-1]
			for j in d:
				try:
					if binary[j] == '1':
						d[j] = 1
				except:
					pass
			l = list(d.keys()).copy()
			for j in l:
				if d[j] == 1:
					d.pop(j)
			if len(d.keys()) == 0:
				break
		ans = firstlen - len(d.keys())
	print(ans)


for i in range(int(input())):
	n = int(input())
	l = [int(x) for x in input().split()]
	a = 0
	for i in l:
		a = a | i
	b = format(a, 'b')
	nl = [int(x) for x in b]
	print(nl.count(1))


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	c = 0
	for i in range(0, n):
		c = c | a[i]
	y = format(c, 'b')
	l = [int(x) for x in str(y)]
	print(l.count(1))


for _ in range(int(input())):
	n = int(input())
	d = 0
	for value in list(set(map(int, input().split()))):
		d |= value
	print(bin(d).count('1'))


t = int(input())
while t > 0:
	n = int(input())
	a = 0
	inp = list(map(int, input().split()))
	for ai in inp:
		a = a | ai
	countsetbits = 0
	while a:
		countsetbits = countsetbits + (a & 1)
		a >>= 1
	print(countsetbits)
	t -= 1


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	s = set()
	count = 0
	for x in a:
		b = bin(x)[2:][::-1]
		for (i, val) in enumerate(b):
			if val == '1':
				if 2 ** i not in s:
					count += 1
					s.add(2 ** i)
	print(count)


from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	ans = 0
	for i in range(32, -1, -1):
		temp = False
		for el in arr:
			if el >> i & 1:
				temp = True
		if temp:
			ans += 1
	print(ans)


import math

def makeZero(l, arr):
	c = 0
	while max(arr) != 0:
		maxIndex = arr.index(max(arr))
		maxElement = arr[maxIndex]
		power = int(math.log(maxElement, 2))
		for i in range(0, l):
			if arr[i] >= 2 ** power:
				arr[i] = arr[i] - 2 ** power
		c = c + 1
	print(c)
ntc = int(input())
for i in range(0, ntc):
	length = int(input())
	array = list(map(int, input().split(' ')))
	makeZero(length, array)


t = int(input())
for i in range(t):
	c = 0
	n = int(input())
	a = input().split()
	a = set(map(int, a))
	a.discard(0)
	while len(a) > 0:
		c += 1
		p = 0
		num = max(a)
		num = num // 2
		while num > 0:
			p += 1
			num = num // 2
		p = 2 ** p
		temp_a = set()
		for ai in a:
			if ai > p:
				temp_a.add(ai - p)
			elif ai < p:
				temp_a.add(ai)
		a = temp_a
	print(c)


t = int(input())
for i in range(t):
	n = int(input())
	l = [int(x) for x in input().split()]
	c = 0
	while any(l):
		cnt = 0
		m = max(l)
		while m > 1:
			m = m // 2
			cnt = cnt + 1
		l = [i % 2 ** cnt for i in l]
		c = c + 1
	print(c)


import sys

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

def main():
	for _ in range(int(_input())):
		n = int(_input())
		ans = 0
		lst = list(map(int, _input().split()))
		for i in lst:
			ans |= i
		j = bin(ans)
		print(j.count('1'))
main()


for _ in range(int(input())):
	a = int(input())
	b = list(map(int, input().split()))[:a]
	d = 0
	for i in range(a):
		d = d | b[i]
	print(bin(d).count('1'))


import math

def func(n, a):
	m = max(a)
	if m == 0:
		return 0
	d = int(math.log(m, 2)) + 1
	temp = [0 for i in range(d)]
	for i in range(n):
		for k in range(d - 1, -1, -1):
			if a[i] & 2 ** k != 0:
				temp[k] = 1
	return temp.count(1)
q = int(input())
for i in range(q):
	n = int(input())
	a = list(map(int, input().split()))
	print(func(n, a))


T = int(input())
for t in range(T):
	N = int(input())
	i = [int(i) for i in input().split()]
	op = 0
	while max(i) > 0:
		m = max(i)
		p = 0
		while pow(2, p) <= m:
			p = p + 1
		v = pow(2, p - 1)
		for n in range(N):
			if i[n] >= v:
				i[n] = i[n] - v
		op = op + 1
	print(op)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	rep = 0
	for i in arr:
		rep = rep | i
	d = bin(rep)
	print(d.count('1'))


for t in range(int(input())):
	N = input()
	A = list(map(int, list(input().split(' '))))
	x = 0
	for i in A:
		x = x | i
	z = x
	c = 0
	while z > 0:
		if z & 1 != 0:
			c = c + 1
		z = z >> 1
	print(c)


import os.path
from math import gcd, floor, ceil
from collections import *
import sys
mod = 1000000007
INF = float('inf')

def st():
	return list(sys.stdin.readline().strip())

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

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

def inp():
	return int(sys.stdin.readline())

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

def prl(n):
	return sys.stdout.write(str(n) + ' ')
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
t = inp()
for i in range(t):
	n = inp()
	l = li()
	s1 = set()
	c = 0
	for i in range(len(l)):
		if l[i] % 2 != 0:
			c = 1
			l[i] -= 1
	for i in l:
		c1 = 0
		i1 = i
		while i > 0:
			i = i // 2
			c1 += 1
		c1 = c1 - 1
		while i1 > 0:
			if pow(2, c1) <= i1:
				i1 = i1 % pow(2, c1)
				s1.add(pow(2, c1))
			c1 = c1 - 1
	pr(len(s1) + c)


t = int(input())
for cases in range(t):
	bits = 0
	ncases = int(input())
	for x in map(int, input().split()):
		bits |= x
	print(bin(bits).count('1'))


t = int(input())
while t > 0:
	n = int(input())
	li = []
	li = list(map(int, input().split()))
	l = []
	max = 0
	for i in range(0, n):
		p = '{0:b}'.format(li[i])
		l.append(p)
		if len(l[i]) > max:
			max = len(l[i])
	for i in range(0, n):
		q = len(l[i])
		if q < max:
			l[i] = (max - q) * '0' + l[i]
	count = 0
	for i in range(0, max):
		for j in range(0, n):
			if l[j][i] == '1':
				count = count + 1
				break
	print(count)
	t = t - 1


import math
for _ in range(int(input())):
	n = int(input())
	list = [int(i) for i in input().split()]
	out = 0
	m = int(math.log2(max(list) + 1)) + 1
	for i in range(m):
		for j in list:
			if j % 2 == 1:
				out += 1
				break
		list = [k // 2 for k in list]
	print(out)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	ans = 0
	for i in l:
		ans = ans | i
	x = '{:032b}'.format(ans)
	print(x.count('1'))


import math as m

def ncr(N, R):
	return m.factorial(N) // (m.factorial(R) * m.factorial(N - R))

def getL():
	return [int(i) for i in input().split(' ')]

def getInt():
	return int(input())

def solve():
	n = getInt()
	arr = getL()
	ans = arr[0]
	for i in range(1, n):
		ans |= arr[i]
	print(bin(ans).count('1'))
for _ in range(getInt()):
	solve()


ncases = int(input())
for case in range(ncases):
	bits = 0
	nvalues = int(input())
	for x in map(int, input().split()):
		bits |= x
	print(bin(bits).count('1'))


for i in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	ans = 0
	for i in arr:
		ans |= i
	c = 0
	while ans:
		c += ans & 1
		ans = ans >> 1
	print(c)


try:
	for _ in range(int(input())):
		n = int(input())
		a = list(map(int, input().split()))
		d = 0
		for i in a:
			d = d | i
		print(bin(d).count('1'))
except:
	pass


t = int(input())
while t:
	n = int(input())
	a = list(map(int, input().split()))
	d = 0
	for i in a:
		d = d | i
	print(bin(d).count('1'))
	t -= 1


from collections import Counter
import string
import math
import bisect
import sys
from fractions import Fraction

def array_int():
	return [int(i) for i in sys.stdin.readline().split()]

def vary(arrber_of_variables):
	if arrber_of_variables == 1:
		return int(sys.stdin.readline())
	if arrber_of_variables >= 2:
		return map(int, sys.stdin.readline().split())

def makedict(var):
	return dict(Counter(var))
mod = 10 ** 9 + 7
testcases = vary(1)
for _ in range(testcases):
	n = vary(1)
	arr = set(array_int())
	power_of_two = odd = 0
	ans = 0
	OR = 0
	for i in arr:
		OR |= i
	print(bin(OR)[2:].count('1'))


t = int(input())
for _ in range(t):
	n = int(input())
	a = map(int, input().split())
	res = 0
	for v in a:
		res |= v
	print(bin(res).count('1'))


t = int(input())
while t != 0:
	t -= 1
	n = int(input())
	l = list(map(int, input().split()))
	a = [0] * 32
	for i in l:
		j = 0
		while j < 32:
			if 1 & i >> j == 1:
				a[j] = 1
			j += 1
	print(a.count(1))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ans = 0
	for j in range(32):
		ok = False
		for v in a:
			ok |= bool(v & 1 << j)
		ans += ok
	print(ans)