Finally, a COVID vaccine is out on the market and the Chefland government has asked you to form a plan to distribute it to the public as soon as possible. There are a total of $N$ people with ages $a_1, a_2, \ldots, a_N$.
There is only one hospital where vaccination is done and it is only possible to vaccinate up to $D$ people per day. Anyone whose age is $\ge 80$ or $\le 9$ is considered to be at risk. On each day, you may not vaccinate both a person who is at risk and a person who is not at risk. Find the smallest number of days needed to vaccinate everyone.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains two space-separated integers $N$ and $D$.
- The second line contains $N$ space-separated integers $a_1, a_2, \ldots, a_N$.

-----Output-----
For each test case, print a single line containing one integer ― the smallest required number of days.

-----Constraints-----
- $1 \le T \le 10$
- $1 \le N \le 10^4$
- $1 \le D \le 10^5$
- $1 \le a_i \le 100$ for each valid $i$

-----Subtasks-----
Subtask #1 (100 points): original constraints

-----Example Input-----
2
10 1
10 20 30 40 50 60 90 80 100 1
5 2
9 80 27 72 79

-----Example Output-----
10
3

-----Explanation-----
Example case 1: We do not need to worry about how the people are grouped, since only one person can be vaccinated in a single day. We require as many days as there are people.
Example case 2: There are two people at risk and three people who are not at risk. One optimal strategy is to vaccinate the two people at risk on day $1$ and the remaining three on the next $2$ days.

Source: codechef | Difficulty: EASY
Tags: Mathematics

Complete search


Solutions:
for i in range(int(input())):
	(y, z) = map(int, input().split())
	l = list(map(int, input().split()))
	risk = 0
	nrisk = 0
	for j in l:
		if j >= 80 or j <= 9:
			risk += 1
	nrisk = y - risk
	h = 0
	h1 = 0
	if risk % z == 0:
		h = risk // z
	else:
		h = risk // z + 1
	if nrisk % z == 0:
		h1 = nrisk // z
	else:
		h1 = nrisk // z + 1
	print(h + h1)


import math
t = int(input())
for _ in range(t):
	(a, b) = map(int, input().split())
	l = list(map(int, input().split()))
	l1 = sorted(l)
	k = 0
	m = 0
	for i in range(0, len(l1)):
		if l1[i] <= 9 or l1[i] >= 80:
			k = k + 1
		else:
			m = m + 1
	x1 = math.ceil(k / b)
	x2 = math.ceil(m / b)
	print(x1 + x2)


for _ in range(int(input())):
	(N, D) = map(int, input().split())
	A = list(map(int, input().split()))
	(count, days) = (0, 0)
	if D == 1:
		print(N)
	else:
		for i in A:
			if i <= 9 or i >= 80:
				count += 1
		if count % D == 0:
			if (N - count) % D == 0:
				days = count // D + (N - count) // D
			else:
				days = count // D + (N - count) // D + 1
		elif (N - count) % D == 0:
			days = count // D + 1 + (N - count) // D
		else:
			days = count // D + 1 + ((N - count) // D + 1)
		print(days)


import math
for _ in range(int(input())):
	(n, d) = list(map(int, input().split(' ')))
	l = list(map(int, input().split(' ')))
	l1 = []
	l2 = []
	for i in l:
		if i >= 80 or i <= 9:
			l1.append(i)
		else:
			l2.append(i)
	x = math.ceil(len(l1) / d)
	y = math.ceil(len(l2) / d)
	print(x + y)


import math
for i in range(int(input())):
	(a, b) = map(int, input().split())
	l = list(map(int, input().split()))
	if b == 1:
		print(a)
	else:
		co = 0
		for j in l:
			if j <= 9 or j >= 80:
				co += 1
		x = math.ceil(co / b)
		y = math.ceil((a - co) / b)
		print(x + y)


t = int(input())
for i in range(t):
	(n, d) = [int(x) for x in input().split()]
	arr = [int(x) for x in input().split()]
	r1 = []
	for j in arr:
		if j <= 9 or j >= 80:
			r1.append(j)
	for j in r1:
		arr.remove(j)
	t = len(r1) // d
	if t != len(r1) / d:
		t = t + 1
	n_t = len(arr) // d
	if n_t != len(arr) / d:
		n_t = n_t + 1
	print(n_t + t)


for i in range(int(input())):
	day = 0
	(N, D) = map(int, input().split())
	x = [int(x) for x in input().split()]
	risk = len(list(filter(lambda j: j >= 80 or j <= 9, x)))
	normal = len(list(filter(lambda j: j > 9 and j < 80, x)))
	while risk != 0:
		if risk <= D:
			risk -= risk
			day += 1
		else:
			x = D % risk
			risk -= x
			day += 1
	while normal != 0:
		if normal <= D:
			normal -= normal
			day += 1
		else:
			x = D % normal
			normal -= x
			day += 1
	print(day)


import math
for i in range(int(input())):
	(n, d) = map(int, input().split())
	list1 = list(map(int, input().split()))
	risk = 0
	not_risk = 0
	for j in list1:
		if j > 79 or j < 10:
			risk += 1
		else:
			not_risk += 1
	print(math.ceil(risk / d) + math.ceil(not_risk / d))


for _ in range(int(input())):
	(f, d) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	risk = 0
	days_risk = 0
	days_norm = 0
	if d == 1:
		print(f)
	else:
		for a in arr:
			if a >= 80 or a <= 9:
				risk += 1
		norm = f - risk
		if risk % d == 0:
			days_risk = risk // d
		else:
			days_risk = risk // d + 1
		if norm % d == 0:
			days_norm = norm // d
		else:
			days_norm = norm // d + 1
		print(days_risk + days_norm)


for i in range(int(input())):
	(n, d) = map(int, input().split())
	l = list(map(int, input().split()))
	count = 0
	for i in range(n):
		if l[i] >= 80 or l[i] <= 9:
			count = count + 1
	notrisky = len(l) - count
	if count % d == 0:
		v = int(count / d)
	else:
		v = int(count / d + 1)
	if notrisky % d == 0:
		w = int(notrisky / d)
	else:
		w = int(notrisky / d + 1)
	print(v + w)


for i in range(int(input())):
	(n, d) = map(int, input().split())
	a = list(map(int, input().split()))
	c = 0
	for i in a:
		if i <= 9 or i >= 80:
			c += 1
	if c % d == 0:
		s = c // d
	else:
		s = c // d + 1
	if (len(a) - c) % d == 0:
		sn = (len(a) - c) // d
	else:
		sn = (len(a) - c) // d + 1
	print(s + sn)


import math as m
T = int(input())
for i in range(T):
	(N, V) = (int(x) for x in input().split())
	ages = list(map(int, input().split(' ')))
	risk = []
	notrisk = []
	for i in ages:
		if i <= 9 or i >= 80:
			risk.append(i)
		else:
			notrisk.append(i)
	print(m.ceil(len(risk) / V) + m.ceil(len(notrisk) / V))


import math
for _ in range(int(input())):
	(n, d) = map(int, input().split())
	ages = list(map(int, input().split()))
	risk = 0
	no_risk = 0
	for i in range(n):
		if ages[i] >= 80 or ages[i] <= 9:
			risk = risk + 1
		else:
			no_risk = no_risk + 1
	days_1 = math.ceil(risk / d)
	days_2 = math.ceil(no_risk / d)
	days = days_1 + days_2
	print(days)


import math
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	l = list(map(int, input().split()))
	p = 0
	for i in l:
		if i >= 80 or i <= 9:
			p = p + 1
	z = math.ceil(p / b)
	c = a - p
	y = math.ceil(c / b)
	print(z + y)


import math
t = int(input())
for _ in range(t):
	(n, d) = map(int, input().split())
	l = list(map(int, input().split()))
	(r, nr) = (0, 0)
	for i in l:
		if i <= 9 or i >= 80:
			r += 1
	nr = n - r
	td = math.ceil(r / d) + math.ceil(nr / d)
	print(td)


for i in range(int(input())):
	(n, d) = map(int, input().split())
	l = list(map(int, input().split()))
	if n == d:
		print(n)
	else:
		count = 0
		risk = []
		for i in l:
			if i >= 80 or i <= 9:
				risk.append(i)
		count += len(risk) // d
		if len(risk) % d > 0:
			count += 1
		k = len(l) - len(risk)
		count += k // d
		if k % d > 0:
			count += 1
		print(count)


for _ in range(int(input())):
	(n, d) = map(int, input().split())
	l = list(map(int, input().split()))
	la = [int(x) for x in l if x <= 9 or x >= 80]
	lb = []
	for i in l:
		if i not in la:
			lb.append(i)
	n = 0
	if len(la) % d:
		n += 1
	n += len(la) // d
	if len(lb) % d:
		n += 1
	n += len(lb) // d
	print(n)


for T in range(int(input())):
	import copy
	(n, d) = [abs(int(n)) for n in input().split()]
	lst = [abs(int(lst)) for lst in input().split()]
	cpy = copy.copy(lst)
	risk = []
	for item in lst:
		if item <= 9 or item >= 80:
			risk.append(item)
			cpy.remove(item)
	import math
	d1 = math.ceil(len(cpy) / d)
	d2 = math.ceil(len(risk) / d)
	print(d1 + d2)


for t in range(int(input())):
	(n, d) = map(int, input().split())
	a = list(map(int, input().split()))
	risk = 0
	for i in range(n):
		if a[i] <= 9 or a[i] >= 80:
			risk += 1
	dr = risk // d
	dnr = (n - risk) // d
	if risk % d != 0:
		dr = dr + 1
	if (n - risk) % d != 0:
		dnr = dnr + 1
	days = dr + dnr
	print(days)


import math
t = int(input())
while t:
	t -= 1
	(n, d) = [int(x) for x in input().split()]
	l = [int(x) for x in input().split()]
	risk = 0
	for i in l:
		if i >= 80 or i <= 9:
			risk += 1
	no_risk = len(l) - risk
	print(math.ceil(no_risk / d) + math.ceil(risk / d))


import math as m
for i in range(int(input())):
	ND = input().split()
	N = int(ND[0])
	D = int(ND[1])
	risk = 0
	L = list(map(int, input().split()))
	if D == 1:
		print(N)
	else:
		for i in L:
			if i <= 9 or i >= 80:
				risk += 1
		print(m.ceil(risk / D) + m.ceil((N - risk) / D))


for _ in range(int(input())):
	(n, d) = map(int, input().split())
	a = list(map(int, input().split()))
	c = 0
	for i in range(n):
		if a[i] <= 9 or a[i] >= 80:
			c += 1
	g = n - c
	if c % d == 0:
		d1 = c // d
	else:
		d1 = c // d + 1
	if g % d == 0:
		d2 = g // d
	else:
		d2 = g // d + 1
	print(d1 + d2)


tc = int(input())
for _ in range(tc):
	(a123, d) = map(int, input().split())
	lis = list(map(int, input().split()))
	risk = 0
	nonrisk = 0
	for k in lis:
		if k > 9 and k < 80:
			nonrisk += 1
		else:
			risk += 1
	daysrequired = risk // d
	if risk % d > 0:
		daysrequired += 1
	daysrequired += nonrisk // d
	if nonrisk % d > 0:
		daysrequired += 1
	print(int(daysrequired))


T = int(input())
for i in range(T):
	(N, D) = map(int, input().split())
	l = list(map(int, input().split()))
	c = 0
	for i in l:
		if i <= 9 or i >= 80:
			c += 1
	s = N - c
	if s % D == 0:
		r1 = s // D
	else:
		r1 = s // D + 1
	if c % D == 0:
		r2 = c // D
	else:
		r2 = c // D + 1
	print(r1 + r2)


t = int(input())
for i in range(t):
	(n, d) = map(int, input().split())
	a = list(map(int, input().split()))
	g = 0
	h = 0
	count = 0
	for j in a:
		if j <= 9 or j >= 80:
			g += 1
		else:
			h += 1
	if g % d == 0:
		count += g // d
	else:
		count += g // d + 1
	if h % d == 0:
		count += h // d
	else:
		count += h // d + 1
	print(count)


import math
for _ in range(int(input())):
	(N, D) = map(int, input().split())
	res = 0
	L = sorted(list(map(int, input().split())))
	S = []
	i = 0
	while L[i] <= 9:
		S.append(L.pop(i))
	i = len(L) - 1
	while L[i] >= 80:
		S.append(L.pop(i))
		i -= 1
		if i < 0:
			break
	res += math.ceil(len(S) / D) + math.ceil(len(L) / D)
	print(res)


t = int(input())
for p in range(t):
	(n, d) = map(int, input().split())
	ages = list(map(int, input().split()))
	at_risk = [age for age in ages if age >= 80 or age <= 9]
	not_at_risk = [age for age in ages if age not in at_risk]
	days = 0
	while at_risk or not_at_risk:
		if at_risk:
			num_vaccinated = min(len(at_risk), d)
			at_risk = at_risk[num_vaccinated:]
			days += 1
		elif not_at_risk:
			num_vaccinated = min(len(not_at_risk), d)
			not_at_risk = not_at_risk[num_vaccinated:]
			days += 1
	print(days)


for i in range(int(input())):
	(n, d) = map(int, input().split())
	l = list(map(int, input().split()))
	l1 = []
	l2 = []
	for j in l:
		if j >= 80 or j <= 9:
			l1.append(j)
		else:
			l2.append(j)
	t1 = len(l1) // d if len(l1) % d == 0 else len(l1) // d + 1
	t2 = len(l2) // d if len(l2) % d == 0 else len(l2) // d + 1
	print(t1 + t2)


for i in range(int(input())):
	(n, d) = map(int, input().split())
	l = list(map(int, input().split()))
	c = 0
	e = 0
	for i in range(n):
		if l[i] >= 80 or l[i] <= 9:
			c += 1
		else:
			e += 1
	if c % d == 0 and e % d == 0:
		print(c // d + e // d)
	elif c % d == 0 or e % d == 0:
		print(c // d + 1 + e // d)
	else:
		print(c // d + e // d + 2)


t = int(input())
for i in range(t):
	(n, d) = map(int, input().split())
	l = list(map(int, input().split()))
	countr = 0
	countn = 0
	for j in range(n):
		if l[j] >= 80 or l[j] <= 9:
			countr += 1
		else:
			countn += 1
	if countr % d != 0:
		countr = int(countr / d) + 1
	else:
		countr = countr / d
	if countn % d != 0:
		countn = int(countn / d) + 1
	else:
		countn = countn / d
	d = countr + countn
	print(int(d))


from math import ceil
for i in range(int(input())):
	(x, y) = map(int, input().split())
	l = list(map(int, input().split()))
	risk = 0
	notrisk = 0
	for i in l:
		if i >= 80 or i <= 9:
			risk += 1
		else:
			notrisk += 1
	print(ceil(risk / y) + ceil(notrisk / y))


import math
t = int(input())
for i in range(t):
	(n, d) = map(int, input().split())
	a = list(map(int, input().split()))
	c_risk = 0
	c_fine = 0
	if d == 1:
		print(n)
	else:
		for j in a:
			if j <= 9 or j >= 80:
				c_risk += 1
			else:
				c_fine += 1
		res = math.ceil(c_risk / d) + math.ceil(c_fine / d)
		print(res)


def covid_vaccine(n, d, ages):
	(risk, not_risk, result) = (0, 0, 0)
	for j in range(n):
		risk += ages[j] >= 80 or ages[j] <= 9
	not_risk = n - risk
	result += int(risk // d) + (risk % d != 0)
	result += int(not_risk // d) + (not_risk % d != 0)
	return result
tc = int(input())
for i in range(tc):
	(n, d) = map(int, input().split())
	ages = list(map(int, input().split()))
	print(covid_vaccine(n, d, ages))


t = int(input())
for _ in range(t):
	(n, d) = map(int, input().split())
	a = list(map(int, input().split()))
	countrisk = 0
	countnotrisk = 0
	for item in a:
		if item <= 9 or item >= 80:
			countrisk = countrisk + 1
		else:
			countnotrisk = countnotrisk + 1
	result = 0
	if countrisk % d == 0:
		result = result + countrisk // d
	else:
		result = result + countrisk // d + 1
	if countnotrisk % d == 0:
		result = result + countnotrisk // d
	else:
		result = result + countnotrisk // d + 1
	print(result)


t = int(input())
for i in range(t):
	(n, d) = map(int, input().split())
	l = [int(x) for x in input().split(' ')]
	c = 0
	for x in l:
		if x <= 9 or x >= 80:
			c += 1
	g = n - c
	if c % d == 0:
		risk = c // d
	else:
		risk = c // d + 1
	if g % d == 0:
		norisk = g // d
	else:
		norisk = g // d + 1
	print(risk + norisk)


import math
for i in range(int(input())):
	(n, d) = map(int, input().split())
	ages = list(map(int, input().split()))
	r = 0
	nr = 0
	for i in range(len(ages)):
		if ages[i] >= 80 or ages[i] <= 9:
			r += 1
		else:
			nr += 1
	print(math.ceil(r / d) + math.ceil(nr / d))


t = int(input())
for i in range(t):
	(n, d) = map(int, input().split())
	l = list(map(int, input().split()))
	m = 0
	for j in l:
		if j >= 80 or j <= 9:
			m += 1
	if m % d == 0:
		if (n - m) % d == 0:
			print(m // d + (n - m) // d)
		else:
			print(m // d + (n - m) // d + 1)
	elif (n - m) % d == 0:
		print(m // d + (n - m) // d + 1)
	else:
		print(m // d + (n - m) // d + 2)


t = int(input())
for _ in range(t):
	(n, d) = map(int, input().split())
	l = list(map(int, input().split()))
	ans = 0
	r = 0
	ans2 = 0
	for i in range(n):
		if l[i] >= 80 or l[i] <= 9:
			r += 1
	nr = n - r
	if r % d == 0:
		ans = r // d
	else:
		ans = r // d + 1
	if nr % d == 0:
		ans2 = nr // d
	else:
		ans2 = nr // d + 1
	print(ans + ans2)


for t in range(int(input())):
	(n, d) = [int(x) for x in input().rstrip().split()]
	a = [int(x) for x in input().rstrip().split()]
	count = 0
	day = 0
	for i in range(0, n):
		if a[i] <= 9:
			count += 1
		elif a[i] >= 80:
			count += 1
		else:
			pass
	n = n - count
	while count != 0:
		if count >= d:
			count -= d
			day += 1
		else:
			day += 1
			break
	while n != 0:
		if n >= d:
			n -= d
			day += 1
		else:
			n = 0
			day += 1
			break
	print(day)


for i in range(int(input())):
	(n, d) = map(int, input().split())
	lst = list(map(int, input().split()))
	(risk, not_risk, ans) = (0, 0, 0)
	for j in range(n):
		if lst[j] >= 80 or lst[j] <= 9:
			risk += 1
		else:
			not_risk += 1
	if risk % d == 0:
		ans += int(risk // d)
	else:
		ans += int(risk // d) + 1
	if not_risk % d == 0:
		ans += int(not_risk // d)
	else:
		ans += int(not_risk // d) + 1
	print(ans)


import math
for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	l = list(map(int, input().split()))
	risk = 0
	non_risk = 0
	for i in range(len(l)):
		if l[i] <= 9 or l[i] >= 80:
			risk += 1
		else:
			non_risk += 1
	print(math.ceil(risk / k) + math.ceil(non_risk / k))


for x in range(int(input())):
	(a, b) = map(int, input().split())
	l = list(map(int, input().split()))
	risk = [x for x in l if x >= 80 or x <= 9]
	not_risk = [x for x in l if x not in risk]
	if len(risk) % b == 0:
		total = len(risk) // b
	else:
		total = len(risk) // b + 1
	if len(not_risk) % b == 0:
		total += len(not_risk) // b
	else:
		total += len(not_risk) // b + 1
	print(total)


t = int(input())
for tc in range(t):
	(n, d) = map(int, input().split())
	x = list(map(int, input().split()))
	c = 0
	for j in x:
		if j <= 9 or j >= 80:
			c += 1
	s = n - c
	if s % d == 0:
		r1 = s // d
	else:
		r1 = s // d + 1
	if c % d == 0:
		r2 = c // d
	else:
		r2 = c // d + 1
	print(r1 + r2)


def ceil(k):
	if k > int(k):
		return int(k) + 1
	else:
		return int(k)
T = int(input())
for _ in range(T):
	risk = 0
	(m, n) = list(map(int, input().split()))
	lst = list(map(int, input().split()))
	for i in lst:
		if i >= 80 or i <= 9:
			risk = risk + 1
	print(ceil(risk / n) + ceil((m - risk) / n))


def numOfRisk(list):
	risk = 0
	for i in list:
		if i <= 9 or i >= 80:
			risk += 1
	return risk
for t in range(int(input())):
	(n, d) = map(int, input().split())
	l = list(map(int, input().split()))
	risk = numOfRisk(l)
	notRisk = n - risk
	(r1, nr1) = (0, 0)
	if risk % d != 0:
		r1 = 1
	if notRisk % d != 0:
		nr1 = 1
	ans = risk // d + notRisk // d + r1 + nr1
	print(ans)


import math
for _ in range(int(input())):
	(n, d) = list(map(int, input().split()))
	m = list(map(int, input().split()))
	risk = 0
	for i in range(len(m)):
		if 80 <= m[i] or m[i] <= 9:
			risk += 1
	print(math.ceil(risk / d) + math.ceil((n - risk) / d))


for tc in range(int(input())):
	(n, d) = map(int, input().split())
	l = list(map(int, input().split()))
	if d == 1:
		print(n)
	else:
		b = len([1 for i in l if i <= 9 or i >= 80])
		x = b // d
		y = (n - b) // d
		if b % d != 0:
			x += 1
		if (n - b) % d != 0:
			y += 1
		print(x + y)


for i in range(int(input())):
	lst = []
	risk = []
	normal = []
	(N, D) = map(int, input().split())
	x = [int(x) for x in input().split()]
	for j in x:
		if j >= 80 or j <= 9:
			risk.append(j)
		else:
			normal.append(j)
	lst2 = []
	while len(risk) != 0:
		if len(lst2) == D:
			lst.append(lst2)
			lst2.clear()
		elif len(risk) == 1:
			p = risk.pop()
			lst2.append(p)
			lst.append(lst2)
			lst2.clear()
		else:
			p = risk.pop()
			lst2.append(p)
	while len(normal) != 0:
		if len(lst2) == D:
			lst.append(lst2)
			lst2.clear()
		elif len(normal) == 1:
			p = normal.pop()
			lst2.append(p)
			lst.append(lst2)
			lst2.clear()
		else:
			p = normal.pop()
			lst2.append(p)
	print(len(lst))


for i in range(int(input())):
	(n, d) = map(int, input().split())
	l = list(map(int, input().split()))
	c = 0
	for i in range(n):
		if l[i] >= 80 or l[i] <= 9:
			c = c + 1
	l1 = n - c
	if c % d == 0:
		d1 = c // d
	else:
		d1 = c // d + 1
	if l1 % d == 0:
		d2 = l1 // d
	else:
		d2 = l1 // d + 1
	print(d1 + d2)


t = int(input())
for i in range(t):
	n_d = input().split(' ')
	ages = input().split(' ')
	(l_risk, l_not_risk) = ([], [])
	for j in range(int(n_d[0])):
		if int(ages[j]) >= 80 or int(ages[j]) <= 9:
			l_risk.append(int(ages[j]))
		else:
			l_not_risk.append(int(ages[j]))
	if len(l_risk) % int(n_d[1]) != 0:
		day_risk = len(l_risk) // int(n_d[1]) + 1
	else:
		day_risk = len(l_risk) // int(n_d[1])
	if len(l_not_risk) % int(n_d[1]) != 0:
		day_not_risk = len(l_not_risk) // int(n_d[1]) + 1
	else:
		day_not_risk = len(l_not_risk) // int(n_d[1])
	print(day_not_risk + day_risk)


for _ in range(int(input())):
	(n, d) = map(int, input().split())
	x = list(map(int, input().split()))
	nr = r = 0
	for age in x:
		if age >= 80 or age <= 9:
			r += 1
		else:
			nr += 1
	minDays = r // d
	if r % d != 0:
		minDays += 1
	minDays += nr // d
	if nr % d != 0:
		minDays += 1
	print(minDays)


import math
for _ in range(int(input())):
	(N, D) = list(map(int, input().split(' ')))
	lst = list(map(int, input().split(' ')))
	if D == 1:
		print(N)
	else:
		lst1 = []
		lst2 = []
		for ele in lst:
			if ele <= 9 or ele >= 80:
				lst1.append(ele)
			else:
				lst2.append(ele)
		x = math.ceil(len(lst1) / D)
		y = math.ceil(len(lst2) / D)
		print(x + y)


for i in range(int(input())):
	risk = 0
	normal = 0
	day = 0
	(N, D) = map(int, input().split())
	x = [int(x) for x in input().split()]
	for j in x:
		if j >= 80 or j <= 9:
			risk += 1
		else:
			normal += 1
	while risk != 0:
		if risk <= D:
			risk -= risk
			day += 1
		else:
			x = D % risk
			risk -= x
			day += 1
	while normal != 0:
		if normal <= D:
			normal -= normal
			day += 1
		else:
			x = D % normal
			normal -= x
			day += 1
	print(day)


t = int(input())
for _ in range(t):
	l1 = []
	l2 = []
	(n, d) = map(int, input().split())
	l = list(map(int, input().split()))
	for i in l:
		if i >= 80 or i <= 9:
			l1.append(i)
		else:
			l2.append(i)
	k1 = len(l1) % d
	k2 = len(l2) % d
	k3 = len(l1) // d
	k4 = len(l2) // d
	if k1 == 0 and k2 == 0:
		print(k3 + k4)
	elif k1 == 0 and k2 != 0:
		print(k3 + k4 + 1)
	elif k1 != 0 and k2 == 0:
		print(k3 + k4 + 1)
	elif k1 != 0 and k2 != 0:
		print(k3 + k4 + 2)


import math
t = int(input())
for i in range(t):
	(n, d) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort()
	c = 0
	for i in l:
		if i <= 9 or i >= 80:
			c = c + 1
	m = len(l) - c
	v1 = math.ceil(m / d)
	v2 = math.ceil(c / d)
	print(v1 + v2)


test = int(input())
for i in range(test):
	(N, D) = map(int, input().split())
	List = list(map(int, input().split()))
	count = 0
	for i in range(N):
		if List[i] <= 9 or List[i] >= 80:
			count += 1
	Normal = N - count
	if count % D == 0:
		d1 = count // D
	else:
		d1 = count // D + 1
	if Normal % D == 0:
		d2 = Normal // D
	else:
		d2 = Normal // D + 1
	print(d1 + d2)


import math
for i in range(int(input())):
	(N, D) = list(map(int, input().split()))
	n = list(map(int, input().split()))
	days = 0
	if D == 1:
		print(len(n))
	else:
		l = [k for k in n if k >= 80 or k <= 9]
		a = math.ceil((len(n) - len(l)) / D)
		b = math.ceil(len(l) / D)
		print(a + b)


import math
t = int(input())
for i in range(t):
	(n, d) = map(int, input().split())
	li = list(map(int, input().split()))
	c = 0
	if d == 1:
		print(n)
	else:
		for v in li:
			if v <= 9 or v >= 80:
				c += 1
		m = math.ceil(c / d)
		n = math.ceil((n - c) / d)
		print(m + n)


T = int(input())
for i in range(T):
	(n, d) = map(int, input().split())
	lst = list(map(int, input().split()))
	c = 0
	for i in lst:
		if i >= 80 or i <= 9:
			c += 1
	rem = n - c
	if c % d == 0:
		s = c // d
	else:
		s = c // d + 1
	if rem % d == 0:
		s1 = rem // d
	else:
		s1 = rem // d + 1
	print(s + s1)


for i in range(int(input())):
	(a, b) = map(int, input().split())
	l = list(map(int, input().split()))
	r = nr = 0
	for i in range(a):
		if l[i] <= 9 or l[i] >= 80:
			r += 1
		else:
			nr += 1
	if r % b == 0:
		k1 = r // b
	else:
		k1 = r // b + 1
	if nr % b == 0:
		k2 = nr // b
	else:
		k2 = nr // b + 1
	print(k1 + k2)


T = int(input())
for _ in range(T):
	(N, D) = map(int, input().split())
	a = list(map(int, input().split()))
	rp = 0
	if N > 1:
		for i in a:
			if i >= 80 or i <= 9:
				rp += 1
		np = N - rp
		np_d = np // D
		rp_d = rp // D
		if np % D > 0:
			np_d += 1
		if rp % D > 0:
			rp_d += 1
		print(np_d + rp_d)
	else:
		print(N)


for _ in range(int(input())):
	(n, d) = map(int, input().split())
	ls = list(map(int, input().split()))
	(r, nr) = (0, 0)
	days = 0
	for i in ls:
		if i <= 9 or i >= 80:
			r += 1
		else:
			nr += 1
	if r % d == 0:
		days += r // d
	else:
		days += r // d + 1
	if nr % d == 0:
		days += nr // d
	else:
		days += nr // d + 1
	print(days)


for i in range(int(input())):
	(N, D) = map(int, input().split())
	arr = list(map(int, input().split()))
	new_arr = []
	for a in arr:
		if a >= 80 or a <= 9:
			new_arr.append(1)
		else:
			new_arr.append(0)
	count0 = 0
	count1 = 0
	for j in new_arr:
		if j == 0:
			count0 += 1
		else:
			count1 += 1
	num = 0
	while count0 > 0:
		num += 1
		count0 -= D
	while count1 > 0:
		num += 1
		count1 -= D
	print(num)


t = int(input())
i = 0
while i < t:
	(n, d) = input().split()
	n = int(n)
	d = int(d)
	a = []
	days = 0
	a = input().split()
	j = 0
	risk = 0
	while j < n:
		x = int(a[j])
		if x >= 80 or x <= 9:
			risk += 1
		j += 1
	nrisk = n - risk
	if risk % d == 0:
		days = int(risk / d)
	else:
		days = int(risk // d) + 1
	if nrisk % d == 0:
		days += int(nrisk / d)
	else:
		days += int(nrisk // d) + 1
	print(days)
	i += 1


n = int(input())
l = []
for i in range(n):
	(N, D) = map(int, input().split())
	lst = list(map(int, input().split()))
	lst.append(D)
	lst.reverse()
	l.append(lst)
import math

def number(li):
	d = li[0]
	li.remove(d)
	risk = []
	non_risk = []
	for i in li:
		if i >= 80 or i <= 9:
			risk.append(i)
		else:
			non_risk.append(i)
	return math.ceil(len(risk) / d) + math.ceil(len(non_risk) / d)
for i in l:
	print(number(i))


for _ in range(int(input())):
	(n, d) = map(int, input().split())
	k = [int(v) for v in input().split()]
	c = 0
	for i in range(n):
		if k[i] <= 9 or k[i] >= 80:
			c = c + 1
	nd = n - c
	if c % d == 0:
		d1 = c // d
	else:
		d1 = c // d + 1
	if nd % d == 0:
		d2 = nd // d
	else:
		d2 = nd // d + 1
	print(d1 + d2)


def a(n):
	if n >= 80 or n <= 9:
		return True
for i in range(int(input())):
	(n, d) = map(int, input().split())
	l = list(map(int, input().split()))
	r = list(filter(a, l))
	nr = [x for x in l if x not in r]
	lr = len(r)
	lnr = len(nr)
	ans = lr // d + lnr // d
	if lr % d != 0:
		ans += 1
	if lnr % d != 0:
		ans += 1
	print(ans)


for _ in range(int(input())):
	(n, d) = map(int, input().split())
	a = list(map(int, input().split()))
	not_rist = []
	at_risk = []
	days = []
	count_days = 0
	count = 0
	for p_age in a:
		if p_age >= 80 or p_age <= 9:
			at_risk.append(p_age)
		else:
			not_rist.append(p_age)
	at_risk_size = len(at_risk)
	not_risk_size = len(not_rist)
	while not_risk_size > 0:
		not_risk_size = not_risk_size - d
		count += 1
	while at_risk_size > 0:
		at_risk_size = at_risk_size - d
		count += 1
	print(count)


t = int(input())
for i in range(0, t):
	(n, d) = map(int, input().split())
	a = list(map(int, input().split()))
	if d == 1:
		print(n)
	else:
		b = len([1 for i in a if i <= 9 or i >= 80])
		p = b // d
		q = (n - b) // d
		if b % d != 0:
			p += 1
		if (n - b) % d != 0:
			q += 1
		print(p + q)


for _ in range(int(input())):
	(days, peoples) = map(int, input().split())
	people = list(map(int, input().split()))
	risk = nrml = 0
	for i in people:
		if i >= 80 or i <= 9:
			risk += 1
		else:
			nrml += 1
	if risk % peoples != 0:
		total = risk // peoples + 1
	if risk % peoples == 0:
		total = risk // peoples
	if nrml % peoples != 0:
		total += nrml // peoples + 1
	if nrml % peoples == 0:
		total += nrml // peoples
	print(total)


import math
for _ in range(int(input())):
	(a, b) = list(map(int, input().split()))
	d = list(map(int, input().split()))[:a]
	l1 = []
	l2 = []
	for i in range(len(d)):
		if d[i] >= 80 or d[i] <= 9:
			l1.append(d[i])
		else:
			l2.append(d[i])
	r1 = math.ceil(len(l1) / b)
	r2 = math.ceil(len(l2) / b)
	print(r1 + r2)


import math
for _ in range(int(input())):
	(n, d) = map(int, input().split())
	arr = list(map(int, input().split()))
	li1 = []
	li2 = []
	for i in arr:
		if i <= 9 or i >= 80:
			li1.append(i)
		else:
			li2.append(i)
	add = math.ceil(len(li1) / d)
	add += math.ceil(len(li2) / d)
	print(add)