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.

Difficulty: interview

Starter code:

Solutions:
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)
    
    


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)

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)


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)



# cook your dish here
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)

# cook your dish here
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<d and len(risk)%d>0):
   count+=1
  k=len(l)-len(risk)
  count+=k//d
  if(k%d>0 and k%d<d):
   count+=1
  print(count)

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)


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

# cook your dish here
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))

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))


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)

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)

# cook your dish here
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))

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))

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 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))
 
 
 


# cook your dish here
import math
t=int(input())
for _ in range(t):
 n,d=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)

# cook your dish here
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)

# cook your dish here
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)
   
  



# 2
# 10 1
# 10 20 30 40 50 60 90 80 100 1
# 5 2
# 9 80 27 72 79
# Example Output
# 10
# 3  


# cook your dish here
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)
   
  



# 2
# 10 1
# 10 20 30 40 50 60 90 80 100 1
# 5 2
# 9 80 27 72 79
# Example Output
# 10
# 3  


# cook your dish here
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)
    


# cook your dish here
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)
  


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))