Read problem statements in [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

Given an array A_{1}, A_{2} \ldots A_{N}, find the minimum number of operations (possibly zero) required to convert all integers in A to 0.

In one operation, you
choose a non-negative integer p (p ≥ 0),
select at most K indices in the array A, and
for each selected index i, replace A_{i} with A_{i}\oplus 2^{p}. Here, \oplus denotes bitwise XOR.

------  Subtasks ------
Subtask #1 (100 points): Original Constraints

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

- The first line contains an integer T - the number of test cases. Then T test cases follow.
- The first line of each test case contains two integers N, K - the size of the array and the maximum number of elements you can select in an operation.
- The second line of each test case contains N integers A_{1}, A_{2} \ldots A_{N}.

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

For each test case, output the minimum number of operations to make all elements of the array 0.

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

$1 ≤ T ≤ 10^{5}$
$1 ≤ N, K ≤ 10^{5}$
$0 ≤ A_{i} ≤ 10^{9}$
- The sum of $N$ over all test cases does not exceed $2\cdot 10^{5}$

----- Sample Input 1 ------ 
1
3 2
3 6 10

----- Sample Output 1 ------ 
5
----- explanation 1 ------ 
Here is one way to achieve $[0, 0, 0]$ from $[3, 6, 10]$ in $5$ operations:
1. Choose $p = 0$ and indices $\{1\}$. Now $A$ becomes $[2, 6, 10]$.
2. Choose $p = 1$ and indices $\{1,2\}$. Now $A$ becomes $[0, 4, 10]$.
3. Choose $p = 1$ and indices $\{3\}$. Now $A$ becomes $[0, 4, 8]$.
4. Choose $p = 2$ and indices $\{2\}$. Now $A$ becomes $[0, 0, 8]$.
5. Choose $p = 3$ and indices $\{3\}$. Now $A$ becomes $[0, 0, 0]$.

It can be shown that at least $5$ operations are required.

Difficulty: MEDIUM
Tags: Bit manipulation

Mathematics
Skill types: Bit manipulation

Starter code:

Solutions:
def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
t = int(input())
while t:
	t -= 1
	(a, b) = input().split()
	(a, b) = (int(a), int(b))
	lis = list(map(int, input().split()))
	bit = [0 for _ in range(32)]
	for i in range(32):
		for j in lis:
			if j & 1 << i:
				bit[i] += 1
	cnt = 0
	for i in bit:
		cnt += (i + b - 1) // b
	print(cnt)


import math
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	ans = 0
	for i in range(32):
		cnt = 0
		for j in l:
			if j >> i & 1 == 1:
				cnt += 1
		ans = ans + math.ceil(cnt / k)
	print(ans)


import math
tests = int(input())
for i in range(tests):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	bits_arr = [0] * 32
	for j in arr:
		count = 0
		while j != 0:
			if j & 1:
				bits_arr[count] += 1
			count += 1
			j >>= 1
	ans = 0
	for j in bits_arr:
		ans += math.ceil(j / k)
	print(ans)


import sys
import math
from functools import cmp_to_key
from collections import OrderedDict
sys.setrecursionlimit(10 ** 9)

def solve():
	for t in range(int(input())):
		(n, k) = list(map(int, input().split()))
		arr = [int(x) for x in input().split()]
		ans = 0
		for i in range(0, 32):
			x = 1 << i
			setBits = 0
			for i in arr:
				if i & x:
					setBits += 1
			ans += math.ceil(setBits / k)
		print(ans)
solve()


import math

def xor(j):
	lo = mo = 0
	lu = []
	k = -1
	for i in j:
		i = int(i)
		while i > 0:
			k = k + 1
			if i % 2 == 1:
				lu.append(k)
			i = i // 2
		k = -1
	lu.sort()
	for i in range(len(lu) - 1):
		if lu[i] != lu[i + 1]:
			lo += math.ceil((i - mo + 1) / int(l[1]))
			mo = i + 1
	print(lo + math.ceil((len(lu) - mo) / int(l[1])))
for forbid in range(int(input())):
	l = input().split()
	xor(input().split())


t = int(input())
while t > 0:
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	bit = [0 for i in range(32)]
	for i in l:
		for x in range(0, 32):
			val = i & 1 << x
			if val != 0:
				bit[x] += 1
	ans = 0
	for i in bit:
		if i % k == 0:
			ans += i // k
		else:
			ans += i // k + 1
	print(ans)
	t -= 1


from math import ceil
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	li = list(map(int, input().split()))
	m = bin(max(li)).lstrip('0b')
	ans = [0] * len(m)
	result = 0
	for i in range(len(ans)):
		for j in range(len(li)):
			if li[j] & 1 << i:
				ans[i] += 1
		result += ceil(ans[i] / k)
	print(result)


import sys
for i in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, sys.stdin.readline().split()))
	m = max(a)
	if m == 0:
		print(0)
		continue
	m = len('{0:b}'.format(m))
	for x in range(n):
		a[x] = '{0:b}'.format(a[x])
		a[x] = '0' * (m - len(a[x])) + a[x]
	r = [0] * m
	for x in range(m):
		for l in a:
			if l[x] == '1':
				r[x] += 1
	ans = 0
	for x in r:
		while x > 0:
			ans += 1
			x -= k
	print(ans)


import math

def function(A, N, K):
	arr = [0 for i in range(50)]
	for num in A:
		i = 0
		while num:
			arr[i] += num & 1
			i += 1
			num = num >> 1
	ans = 0
	for i in range(len(arr)):
		ans += math.ceil(arr[i] / K)
	return ans

def main():
	T = int(input())
	for _ in range(T):
		(N, K) = list(map(int, input().split(' ')))
		A = list(map(int, input().split(' ')))
		val = function(A, N, K)
		print(val)
main()


import math
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	if max(a) == 0:
		print(0)
		continue
	x = int(math.log(max(a), 2))
	d = {}
	for i in range(x + 1):
		d[i] = 0
		for j in range(n):
			if a[j] % 2:
				d[i] += 1
			a[j] //= 2
	ans = 0
	for i in d:
		ans += math.ceil(d[i] / k)
	print(ans)


import math
from bisect import bisect_left
from code import interact
from heapq import heapify, heappush, heappop
from collections import deque
from pydoc import plain
from re import X
import sys
from math import gcd, sqrt, log10, log2, floor, ceil, sqrt
input = sys.stdin.readline

def il():
	return [int(a) for a in input().strip().split()]

def ip():
	return input().strip()

def ii():
	return int(input())

def ot(in_p, *args, e=' '):
	if type(in_p) == list:
		print(*in_p, end=e)
	if type(in_p) == str or type(in_p) == int:
		print(in_p, end=e)
		for l in args:
			print(l, end=e)
	print()

def a_pwr_n(a, n, mod):
	if n == 1:
		return a % mod
	if n % 2 == 0:
		val = a_pwr_n(a, n // 2, mod)
		return val % mod * val % mod
	else:
		return a % mod * a_pwr_n(a, n - 1, mod) % mod

def rg(*ag):
	if len(ag) == 3:
		return range(ag[0], ag[1], ag[2])
	elif len(ag) == 2:
		return range(ag[0], ag[1])
	elif len(ag) == 1:
		return range(ag[0])
	else:
		raise 'invalid input'

def ispal(i, j, st):
	while i <= j:
		if st[i] == st[j]:
			i = i + 1
			j = j - 1
		else:
			return False
	return True
mod = 1000000000 + 7
dx = [-1, -2, 1, 2, 2, -2, -1, 1]
dy = [2, 1, 2, 1, -1, -1, -2, -2]
for _ in range(ii()):
	(n, k) = il()
	a = il()
	l = [0] * 30
	for i in range(n):
		b = '{0:b}'.format(a[i])
		b = list(map(int, str(b)))
		p = len(l) - 1
		for j in range(len(b) - 1, -1, -1):
			l[p] += b[j]
			p -= 1
	s = 0
	for i in range(len(l)):
		s += math.ceil(l[i] / k)
	print(s)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = [*map(int, input().split())]
	q = [0] * 32
	for i in a:
		p = 0
		while i:
			q[p] += i & 1
			i >>= 1
			p += 1
	print(sum(((i + k - 1) // k for i in q)))


import math
a = int(input())
for i in range(a):
	(n, k) = map(int, input().split())
	v = list(map(int, input().split()))
	bits = [0 for j in range(32)]
	for u in range(32):
		for p in range(len(v)):
			if v[p] % 2 != 0:
				bits[u] += 1
			v[p] = v[p] // 2
	print(sum([math.ceil(hey / k) for hey in bits]))


import math
t = int(input())
for i in range(t):
	(n, k) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	r = 0
	for j in range(32):
		ans = 0
		for z in a:
			ans += z & pow(2, j) > 0
		r += math.ceil(ans / k)
	print(r)


import math

def solve(n, k, arr):
	res = 0
	for idx in range(32):
		ans = 0
		for num in arr:
			ans += num & pow(2, idx) > 0
		res += math.ceil(ans / k)
	return res
for i in range(int(input())):
	(n, k) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	print(solve(n, k, arr))


import math
testcase = int(input())
for t in range(testcase):
	(n, k) = map(int, input().split())
	ar = list(map(int, input().split()))
	ans = 0
	for i in range(32):
		bit_sum = 0
		for j in range(n):
			bit = ar[j] & pow(2, i) > 0
			bit_sum += bit
		ans += int(math.ceil(bit_sum / k))
	print(ans)


import math
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	(p, h) = (0, len(bin(max(arr))) - 2)
	ans = 0
	while p < h:
		cur = 1 << p
		cnt = 0
		for i in range(n):
			if arr[i] & cur == cur:
				arr[i] ^= cur
				cnt += 1
		ans += math.ceil(cnt / k)
		p += 1
	print(ans)


import math
for i in range(int(input())):
	(N, k) = map(int, input().split())
	array = list(map(int, input().split()))
	m = array.index(max(array))
	array = list(map(lambda x: str(bin(x)[2:]), array))
	total = [0] * 32
	for j in range(len(array)):
		array[j] = array[j].rjust(len(array[m]), '0')
	for i in range(len(array[m])):
		for j in array:
			total[i] += int(j[i])
	result = 0
	for j in total:
		result += math.ceil(int(j) / float(k))
	print(result)


for _ in range(int(input())):
	(N, K) = map(int, input().split())
	cnt = [0] * 30
	A = [*map(int, input().split())]
	for x in A:
		for j in range(30):
			if x >> j & 1:
				cnt[j] += 1
	print(sum(((x + K - 1) // K for x in cnt)))


import math
t = int(input())
while t:
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	msb = [0 for i in range(40)]
	for i in range(n):
		for j in range(30, -1, -1):
			if arr[i] & 1 << j:
				msb[j] += 1
	ans = 0
	for i in msb:
		if i:
			if i <= k:
				ans += 1
			else:
				ans += math.ceil(i / k)
	print(ans)
	t -= 1


from math import ceil
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	l = [int(x) for x in input().split()]
	f = [0] * 32
	for ele in l:
		b = '{:032b}'.format(ele)
		for (ind, ch) in enumerate(b):
			if ch == '1':
				f[ind] += 1
	ans = 0
	for i in f:
		ans += ceil(i / k)
	print(ans)


import math
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	k = float(k)
	a = list(map(int, input().split()))
	res = 0
	for i in range(len(bin(max(a))) - 2):
		c = 0
		for j in a:
			p = 2 ** i
			if j & p != 0:
				c += 1
		c = float(c)
		res += math.ceil(c / k)
	print(res)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	bin = [0] * 32
	for y in range(32):
		for j in a:
			if j & 1 << y:
				bin[y] += 1
	res = 0
	for i in bin:
		if i % k == 0:
			res += i // k
		else:
			res += i // k + 1
	print(res)


import math
T = int(input())
for tc in range(T):
	(n, k) = map(int, input().split(' '))
	seq = list(map(int, input().split(' ')))
	count = 0
	bit_count = [0] * 32
	for j in range(32):
		for i in range(n):
			if seq[i] & 1 == 1:
				bit_count[j] = bit_count[j] + 1
			seq[i] = seq[i] >> 1
		count = count + math.ceil(bit_count[j] / k)
	print(count)


import math
try:
	for _ in range(int(input())):
		(n, k) = list(map(int, input().split()))
		arr = list(map(int, input().split()))
		temp = []
		for i in arr:
			if i == 1:
				binary_form = '0' * 31 + '1'
			else:
				bits = len(bin(i).replace('0b', ''))
				binary_form = '0' * (32 - bits) + bin(i).replace('0b', '')
			temp.append(binary_form)
		cnt = []
		for i in range(32):
			ones = 0
			for j in range(n):
				if temp[j][i] == '1':
					ones += 1
			if ones % k == 0:
				cnt.append(ones // k)
			else:
				cnt.append(ones // k + 1)
		print(sum(cnt))
except:
	pass


import math
for T in range(int(input())):
	(n, k) = map(int, input().split())
	(a, b) = (list(map(int, input().split())), [0] * 32)
	for z in a:
		p = 0
		while z > 0:
			if z & 1:
				b[p] += 1
			z = z >> 1
			p += 1
	print(sum([math.ceil(z / k) for z in b]))


n = int(input())
for i in range(n):
	(N, P) = map(int, input().split())
	l = list(map(int, input().split()))
	a = 0
	q = []
	for i in range(N):
		p = bin(l[i])
		p = p[2:]
		W = len(p)
		q.append((32 - W) * '0' + p)
	for i in range(32):
		c = 0
		for j in range(N):
			if q[j][i] == '1':
				c += 1
		if c % P == 0:
			a += c // P
		else:
			a += c // P + 1
	print(a)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	x = list(map(int, input().split()))
	xd = {}
	for i in range(n):
		if x[i] > 0:
			temp = bin(x[i])[2:]
			for j in range(len(temp) - 1, -1, -1):
				if temp[j] == '1':
					xd[len(temp) - 1 - j] = xd.setdefault(len(temp) - 1 - j, 0) + 1
	ans = 0
	for i in xd.values():
		if i % k > 0:
			ans += i // k + 1
		else:
			ans += i // k
	print(ans)


for t in range(int(input())):
	(N, k) = map(int, input().split())
	l = list(map(int, input().split()))
	data = {}
	for x in l:
		b = str(bin(x))
		w = b[2:][::-1]
		q = 0
		for i in w:
			if i == '1':
				try:
					data[q] += 1
				except:
					data[q] = 1
			q += 1
	ans = 0
	for i in data.keys():
		if data[i] % k == 0:
			ans += data[i] // k
		else:
			ans += data[i] // k + 1
	print(ans)


for t in range(int(input())):
	(n, k) = list(map(int, input().split()))
	l = list(map(int, input().split()))
	one = {}
	for i in l:
		p = str(bin(i))
		w = p[2:][::-1]
		q = 0
		for j in w:
			if j == '1':
				try:
					one[q] += 1
				except:
					one[q] = 1
			q += 1
	total = 0
	for i in one.keys():
		if one[i] % k == 0:
			total += one[i] // k
		else:
			total += one[i] // k + 1
	print(total)


from collections import defaultdict

def seal(a, b):
	return (a + b - 1) // b
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = [int(x) for x in input().split()]
	d = defaultdict(int)
	for i in arr:
		pos = 0
		while i != 0:
			if i & 1:
				d[pos] += 1
			i >>= 1
			pos += 1
	ans = 0
	for (key, value) in d.items():
		ans += seal(value, k)
	print(ans)


from sys import stdin, stdout
from heapq import heapify, heappush, heappop
import sys
from collections import Counter
from copy import deepcopy
import math
sys.setrecursionlimit(10 ** 5)

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

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

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

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

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

def intinput():
	return int(stdin.readline().strip())
for test in range(intinput()):

	def solve():
		(n, k) = mapinput()
		arr = listinput()
		posi = Counter()
		for tt in range(35):
			for i in range(n):
				if arr[i] & 1 == 1:
					posi[tt] += 1
				arr[i] = arr[i] >> 1
		ans = 0
		for i in posi:
			ans += math.ceil(posi[i] / k)
		print(ans)
	solve()


no_of_cases = int(input())
for i in range(0, no_of_cases):
	(lenght, operation) = map(int, input().split())
	arr = list(map(int, input().split()))
	steps = 0
	for k in range(0, 32):
		count = 0
		for index in range(0, lenght):
			if arr[index] % 2 == 0:
				arr[index] = arr[index] / 2
			else:
				count += 1
				arr[index] = arr[index] // 2
		steps += count / operation if count % operation == 0 else count // operation + 1
	print(int(steps))


t = int(input())
while t:
	t -= 1
	ans = 0
	(N, K) = input().split()
	n = int(N)
	k = int(K)
	arr = [int(i) for i in input().split()]
	for i in range(32):
		count = 0
		for j in range(n):
			if arr[j] != 0:
				if arr[j] & 1:
					count += 1
				arr[j] = int(arr[j] / 2)
		ans += int((count + k - 1) / k)
	print(ans)


import math
noOfTestCases = int(input())
for i in range(noOfTestCases):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	res = 0
	for j in range(max(a) // 2 + 1):
		cnt = 0
		for i in range(n):
			if a[i] & 1:
				cnt += 1
			a[i] = a[i] // 2
		res = res + math.ceil(cnt / k)
		if sum(a) == 0:
			break
	print(res)


import math
k = int(input())
for a in range(k):
	s = [int(x) for x in input().split()]
	d = [int(x) for x in input().split()]
	dic = {}
	for i in range(s[0]):
		num = d[i]
		k = 1
		while num != 0:
			if num % 2 == 1:
				if k in dic:
					dic[k] += 1
				else:
					dic[k] = 1
			num = num // 2
			k += 1
	total = 0
	for i in dic:
		total += math.ceil(dic[i] / s[1])
	print(total)


t = int(input())
for _ in range(t):
	(n, k) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	tot = [0] * 32
	for item in arr:
		z = item
		ind = 0
		while z:
			if z & 1:
				tot[ind] += 1
			z = z >> 1
			ind += 1
	ans = 0
	for item in tot:
		if item % k == 0:
			ans += item // k
		else:
			ans += item // k + 1
	print(ans)


for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	l = list(map(int, input().split()))
	one = {}
	for i in l:
		num = str(bin(i))
		bNum = num[2:][::-1]
		q = 0
		for j in bNum:
			if j == '1':
				try:
					one[q] += 1
				except:
					one[q] = 1
			q += 1
	total = 0
	for i in one.keys():
		if one[i] % k == 0:
			total += one[i] // k
		else:
			total += one[i] // k + 1
	print(total)


t = int(input())
while t:
	t -= 1
	l = [int(i) for i in input().split(' ')]
	n = l[0]
	k = l[1]
	a = [int(i) for i in input().split(' ')]
	sm = 0
	for _ in range(32):
		count = 0
		for i in range(n):
			if a[i] != 0:
				count += a[i] & 1
			a[i] = a[i] >> 1
		sm = sm + (count + k - 1) // k
	print(sm)


from math import *
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	bit = [0] * 32
	for i in range(32):
		for j in range(n):
			if a[j] % 2 != 0:
				bit[i] += 1
			a[j] = a[j] // 2
	ans = 0
	for i in range(32):
		ans += ceil(bit[i] / k)
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = [int(x) for x in input().split()]
	b = []
	for i in range(0, 31):
		b.append(0)
		for j in range(n):
			if a[j] % 2 != 0:
				b[i] += 1
			a[j] = a[j] // 2
	ans = 0
	for i in range(0, 31):
		if b[i] % k == 0:
			ans += b[i] // k
		else:
			ans += b[i] // k + 1
	print(ans)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	l = [int(i) for i in input().split()]
	binary = []
	for i in l:
		binary.append(bin(i).replace('0b', ''))
	res = [0 for i in range(32)]
	for i in range(n):
		tmp = binary[i]
		c = 31
		for i in range(len(tmp) - 1, -1, -1):
			if tmp[i] == '1':
				res[c] += 1
			c -= 1
	ans = 0
	for i in res:
		if i > 0:
			if i % k == 0:
				ans += i // k
			else:
				ans += i // k + 1
	print(ans)


import math

def solve():
	(n, k) = [int(x) for x in input().split()]
	a = list(map(int, input().split()))
	c = [0] * 32
	for x in a:
		for i in range(30):
			if x & 1 << i > 0:
				c[i] += 1
	ans = 0
	for x in c:
		ans = ans + math.ceil(x / k)
	print(ans)
	return
t = int(input())
for i in range(t):
	solve()


from math import *
for j in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	bitarr = [0] * 32
	for i in range(32):
		for item in arr:
			if item & 1 << i:
				bitarr[i] += 1
	total = 0
	for item in bitarr:
		total += ceil(item / k)
	print(total)


from sys import stdin
from collections import defaultdict
import math

def highestPowerof2(n):
	p = int(math.log(n, 2))
	return [p, int(pow(2, p))]

def processNum(num, dic, n, k):
	nearest2pow = highestPowerof2(num)
	tmp = num - nearest2pow[1]
	dic[str(nearest2pow[0])] += 1
	while tmp != 0:
		nearest2pow = highestPowerof2(tmp)
		tmp = tmp - nearest2pow[1]
		dic[str(nearest2pow[0])] += 1
dic = defaultdict(int)
t = int(stdin.readline())
while t:
	dic.clear()
	(n, k) = [int(x) for x in stdin.readline().split()]
	arr = [int(x) for x in stdin.readline().split()]
	for num in arr:
		if num > 0:
			processNum(num, dic, n, k)
	final_ans = 0
	for (key, val) in dic.items():
		if val % k == 0:
			final_ans += val // k
		else:
			final_ans += val // k + 1
	print(final_ans)
	t -= 1


t = int(input())
for i in range(t):
	(n, ki) = map(int, input().split())
	a = list(map(int, input().split()))
	l = []
	for j in range(n):
		l.append(bin(a[j]).replace('0b', ''))
	for b in range(n):
		l[b] = int(l[b])
	ans = 0
	m = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
	for x in range(0, n):
		for k in range(0, 31):
			if l[x] != 0:
				m[k] += l[x] % 10
				l[x] = l[x] // 10
	for z in range(0, 31):
		if m[z] % ki == 0:
			ans += m[z] // ki
		else:
			ans += m[z] // ki + 1
	print(ans)


import math
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	p = [0] * 30
	for i in a:
		s = bin(i)
		s = s[:1:-1]
		for c in range(len(s)):
			p[c] += int(s[c])
	ans = 0
	for i in p:
		ans += math.ceil(i / k)
	print(ans)


we = int(input())
for i in range(we):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	c = 0
	g = []
	for i in l:
		d = str(bin(i))
		d = d[2:]
		g.append([d, len(d)])
		if len(d) > c:
			c = len(d)
	r = []
	for i in g:
		y = []
		for j in range(c - i[1]):
			y.append('0')
		for j in i[0]:
			y.append(j)
		r.append(y)
	s = 0
	for i in range(c):
		f = 0
		for j in range(len(l)):
			if r[j][i] == '1':
				f += 1
		if f % k != 0:
			s = s + 1 + f // k
		else:
			s = s + f // k
	print(s)


import math

def ans():

	def binary(a):
		bn = bin(a).replace('0b', '')
		x = bn[::-1]
		while len(x) < 8:
			x += '0'
		bn = x[::-1]
		return bn
	(N, K) = map(int, input().split())
	A = list(map(int, input().split()))
	plraw = []
	for i in A:
		bi = binary(i)
		bir = bi[::-1]
		for j in range(len(bi)):
			if bir[j] == '1':
				plraw.append(j)
	plc = []
	for i in plraw:
		if i not in plc:
			plc.append(i)
	sum = 0
	for i in plc:
		cnt = plraw.count(i)
		sum = sum + math.ceil(cnt / K)
	return sum
T = int(input())
for i in range(T):
	an = ans()
	print(an)


t = int(input())
for i in range(t):
	x = input().split()
	(n, k) = tuple(map(int, x))
	x = input().split()
	a = list(map(int, x))
	ele = []
	for j in range(0, 31):
		ele.append(0)
		for p in range(0, n):
			if a[p] % 2 != 0:
				ele[j] += 1
			a[p] = int(a[p] / 2)
		res = 0
	for j in range(0, 31):
		if ele[j] % k == 0:
			res += ele[j] / k
		else:
			res += int(ele[j] / k) + 1
	print(int(res))


from math import *
for u in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	s = []
	m = 0
	for i in range(n):
		b = bin(l[i])[2:]
		m = max(len(b), m)
		s.append(b)
	for i in range(n):
		if len(s[i]) < m:
			s[i] = '0' * (m - len(s[i])) + s[i]
	d = []
	for j in range(m):
		c = 0
		for i in range(n):
			if s[i][j] == '1':
				c += 1
		d.append(c)
	q = 0
	for i in range(m):
		q += ceil(d[i] / k)
	print(q)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	s = [0 for i in range(32)]
	for i in a:
		temp = bin(i).replace('b', '0')
		l = 0
		for i in range(len(temp) - 1, -1, -1):
			s[31 - l] += int(temp[i])
			l += 1
	ans = 0
	for i in s:
		if i > 0:
			if i > k:
				if i % k == 0:
					ans += i // k
				else:
					ans += i // k + 1
			else:
				ans += 1
	print(ans)


t = int(input())
for _ in range(t):
	inn = input()
	(n, k) = map(int, inn.split(' '))
	inn = input()
	arr = list(map(int, inn.split(' ')))
	total = 0
	res = 0
	for i in range(0, 32):
		total = 0
		for j in range(0, len(arr)):
			if arr[j] & 1:
				total += 1
			arr[j] = arr[j] >> 1
		if total % k == 0:
			res += total // k
		else:
			res += total // k + 1
	print(res)


T = int(input())
while T:
	(n, k) = map(int, input().split(' '))
	arr = map(int, input().split(' '))
	ans = 0
	d = {}
	for i in arr:
		bn = bin(i).replace('0b', '')[::-1]
		for j in range(len(bn)):
			if bn[j] == '0':
				continue
			if j in d:
				d[j] += 1
			else:
				d[j] = 1
	for (key, itm) in d.items():
		if itm <= k:
			ans += 1
		else:
			while itm > k:
				itm = itm - k
				ans += 1
			if itm > 0:
				ans += 1
	print(ans)
	T -= 1


import math
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	bits = [0] * 32
	for i in range(n):
		for j in range(32):
			if arr[i] & 1 << j:
				bits[j] += 1
	ans = 0
	for i in range(32):
		ans = ans + math.ceil(bits[i] / k)
	print(ans)


t = int(input())
final = []
for _ in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	max_len = len(bin(max(a))[2:])
	for x in range(n):
		a[x] = bin(a[x])[2:]
	for x in range(n):
		if len(a[x]) < max_len:
			p = max_len - len(a[x])
			a[x] = '0' * p + a[x]
	ans = 0
	for x in range(max_len):
		count = 0
		for y in range(n):
			if a[y][x] == '1':
				count += 1
		if int(count / k) == count / k:
			ans += int(count / k)
		else:
			ans += int(count / k) + 1
	final.append(ans)
for _ in range(t):
	print(final[_])


t = int(input())
while t > 0:
	t -= 1
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	lst = [0] * 32
	for x in arr:
		i = 0
		while x:
			lst[i] += x & 1
			x >>= 1
			i += 1
	ans = 0
	for x in lst:
		ans += (x + k - 1) // k
	print(ans)


from collections import Counter
from math import ceil

def go():
	(n, k) = map(int, input().split())
	count = Counter()
	for x in map(int, input().split()):
		i = 0
		while x:
			if x & 1:
				count[i] += 1
			x >>= 1
			i += 1
	return sum((ceil(v / k) for v in count.values()))
cases = int(input())
for _ in range(cases):
	print(go())


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

def count(A, K):
	A_bin = []
	p = len(str(decimalToBinary(max(A))))
	for i in A:
		A_bin.append(str(decimalToBinary(i)).rjust(p, '0'))
	ans = 0
	for i in range(p):
		count = 0
		for j in A_bin:
			if j[i] == '1':
				count += 1
		ans += (count + K - 1) // K
	return ans
T = int(input())
for _ in range(T):
	(N, K) = [int(x) for x in input().split()]
	A = [int(y) for y in input().split()]
	print(count(A, K))


try:
	for i in range(int(input())):
		(n, k) = map(int, input().split())
		arr = list(map(int, input().split()))
		binary = []
		for i in range(0, 31):
			binary.append(0)
			for j in range(n):
				if arr[j] % 2 != 0:
					binary[i] += 1
				arr[j] = arr[j] // 2
		ans = 0
		for i in range(0, 31):
			if binary[i] % k == 0:
				ans += binary[i] // k
			else:
				ans += binary[i] // k + 1
		print(ans)
except:
	pass


import math
t = int(input())
for _ in range(t):
	(N, K) = map(int, input().split())
	a = list(map(int, input().split()))
	bitcnt = [0] * 32
	for i in a:
		bitpos = 0
		while i > 0:
			if i & 1:
				bitcnt[bitpos] += 1
			i >>= 1
			bitpos += 1
	ans = 0
	for i in bitcnt:
		ans += -1 * i // K * -1
	print(ans)


from collections import defaultdict
import math
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	D = defaultdict(lambda : 0)
	for i in range(n):
		val = bin(arr[i])[2:].rjust(30, '0')
		for j in range(30):
			if val[29 - j] == '1':
				D[j] += 1
	ans = 0
	for ele in D:
		x = math.ceil(D[ele] / k)
		ans += x
	print(ans)


import math
t = int(input())
for i in range(t):
	bin_count = {}
	res = 0
	(n, k) = map(int, input().split())
	array = list(map(int, input().split()))
	for number in array:
		bin_num = bin(number)[2:]
		length = len(bin_num)
		for (index, i) in enumerate(bin_num):
			if i == '1':
				bin_count[length - index] = bin_count.get(length - index, 0) + 1
	for value in bin_count.values():
		if value == 1:
			res += 1
		else:
			res += math.ceil(value / k)
	print(res)


from math import ceil
tc = 1
tc = int(input())
for _ in range(tc):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	bit_cnt = [0] * 32
	for i in a:
		bit_pos = 0
		while i > 0:
			if i & 1:
				bit_cnt[bit_pos] += 1
			i >>= 1
			bit_pos += 1
	ans = 0
	for i in bit_cnt:
		ans += ceil(i / k)
	print(ans)


test_case = int(input())
for i in range(test_case):
	(n, k) = map(int, input().split())
	lst = tuple(map(int, input().split()))
	binary_cnt = [0] * 32
	for j in lst:
		count = 0
		while j > 0:
			if j & 1 == 1:
				binary_cnt[count] += 1
			j = j // 2
			count += 1
	ans = 0
	for l in binary_cnt:
		if l > 0:
			ka = min(l, k)
			if l % ka == 0:
				ans += l // ka
			else:
				ans += l // ka + 1
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split(' '))
	arr = list(map(int, input().split(' ')))
	carr = [0 for i in range(32)]
	for i in arr:
		bnum = bin(i)[2:][::-1]
		for j in range(len(bnum)):
			carr[j] += int(bnum[j])
	ans = 0
	for i in carr:
		ans += (i + k - 1) // k
	print(ans)


t = int(input())
for _ in range(t):
	(n, k) = input().split()
	n = int(n)
	k = int(k)
	arr = list(map(int, input().split()))
	count_arr = [0 for _ in range(32)]
	for v in arr:
		for i in range(32):
			if v & 1 << i:
				count_arr[i] += 1
	ans = 0
	for i in range(32):
		if count_arr[i] >= k:
			ans += count_arr[i] // k
			if count_arr[i] % k != 0:
				ans += 1
		elif count_arr[i] != 0:
			ans += 1
	print(ans)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	op_num = 0
	p = 0
	while p != -1:
		ones_to_change = 0
		for j in range(n):
			if a[j]:
				ones_to_change += a[j] % 2
				a[j] //= 2
		op_num += -(-ones_to_change // k)
		p += 1
		if any(a):
			continue
		break
	print(op_num)


import math
I = input

def solve():
	(n, k) = map(int, I().split())
	a = list(map(int, I().split()))
	sol = 0
	for i in range(0, 32):
		count = 0
		for j in range(n):
			if a[j] != 0:
				if a[j] & 1:
					count += 1
				a[j] = a[j] // 2
		sol += math.ceil(count / k)
	return sol
for _ in range(int(I())):
	print(solve())