Chef wants to host some Division-3 contests. Chef has $N$ setters who are busy creating new problems for him. The $i^{th}$ setter has made $A_i$ problems where $1 \leq i \leq N$.    
A Division-3 contest should have exactly $K$ problems. Chef wants to plan for the next $D$ days using the problems that they have currently. But Chef cannot host more than one Division-3 contest in a day.
Given these constraints, can you help Chef find the maximum number of Division-3 contests that can be hosted in these $D$ days?

-----Input:-----
- The first line of 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 three space-separated integers - $N$, $K$ and $D$ respectively.
- The second line of each test case contains $N$ space-separated integers $A_1, A_2, \ldots, A_N$ respectively. 

-----Output:-----
For each test case, print a single line containing one integer ― the maximum number of Division-3 contests Chef can host in these $D$ days.

-----Constraints-----
- $1 \leq T \leq 10^3$
- $1 \leq N \leq 10^2$
- $1 \le K \le 10^9$ 
- $1 \le D \le 10^9$
- $1 \le A_i \le 10^7$ for each valid $i$

-----Subtasks-----
Subtask #1 (40 points):
- $N = 1$
- $1 \le A_1 \le 10^5$
Subtask #2 (60 points): Original constraints

-----Sample Input:-----
5
1 5 31
4
1 10 3
23
2 5 7
20 36
2 5 10
19 2
3 3 300
1 1 1

-----Sample Output:-----
0
2
7
4
1

-----Explanation:-----
- 
Example case 1: Chef only has $A_1 = 4$ problems and he needs $K = 5$ problems for a Division-3 contest. So Chef won't be able to host any Division-3 contest in these 31 days. Hence the first output is $0$.
- 
Example case 2: Chef has $A_1 = 23$ problems and he needs $K = 10$ problems for a Division-3 contest. Chef can choose any $10+10 = 20$ problems and host $2$ Division-3 contests in these 3 days. Hence the second output is $2$.
- 
Example case 3: Chef has $A_1 = 20$ problems from setter-1 and $A_2 = 36$ problems from setter-2, and so has a total of $56$ problems. Chef needs $K = 5$ problems for each Division-3 contest. Hence Chef can prepare $11$ Division-3 contests. But since we are planning only for the next $D = 7$ days and Chef cannot host more than $1$ contest in a day, Chef cannot host more than $7$ contests. Hence the third output is $7$.

Difficulty: interview

Starter code:

Solutions:
for T in range(int (eval(input()))):
 N,K,D=list(map(int,input().split()))
 A=list(map(int,input().split()))
 P=sum(A)//K 
 print(min(P,D))


# cook your dish here
#Hello
r=int(input())
while r>0:
 n,k,d=map(int,input().split())
 l=list(map(int,input().split()))[0:n]
 sum=0
 for x in range(n):
  sum=sum+l[x]
 c=sum//k
 if (c>=d):
  print(d)
 else: print(c)
 r-=1
"""""
5
1 5 31
4
1 10 3
23
2 5 7
20 36
2 5 10
19 2
3 3 300
1 1 1
"""""

# cook your dish here
test=int(input())
while(test!=0):
 n,k,d=list(map(int,input().split()))
 li=list(map(int,input().split()))
 days=sum(li)//k 
 print(min(days,d))
 test=test-1 


t=int(input())
for x in range(0,t):
 n,k,d=list(map(int,input().split()))
 noofq=list(map(int,input().split()))
 sum1=0
 poss=0
 for j in range(n):
  sum1=sum1+noofq[j]
 if(sum1>=k):
  poss=sum1//k
 else:
  poss=0
 if(poss>d):
  poss=d
 print(poss)


for i in range(int(input())):
 n,k,d = map(int, input().split())
 l = list(map(int,input().split()))
 t = sum(l)
 if t < k :
  print("0")
 elif t == k:
  print("1")
 elif t>k:
  a = t//k
  if a >= d:
   print(str(d))
  else:
   print(str(a))

t=int(input())
for _ in range(t):
 nkd= list(map(int,input().split()))
 k=nkd[1]
 d=nkd[2]
 an= list(map(int,input().split()))
 sum1=sum(an)
 if sum1<k:
  print("0")
 else:
  a = sum1//k 
  if a>d:
   print(d)
  else:
   print(a)
 
 


T = int(input())
for i in range(T):
 n,k,d = [int(x) for x in input().split()]
 A = [int(x) for x in input().split()]
 s = sum(A)
 if(s//k<d):
  print(s//k)
 else:
  print(d)


# cook your dish here

for _ in range(int(input())):
 l=list(map(int,input().split()))
 a=list(map(int,input().split()))
 s=sum(a)
 d=s//l[1]
 
 if(d>l[2]):
  print(l[2])
 else:
  print(d)


# cook your dish here
for _ in range(int(input())):
 n,k,d = list(map(int,input().split()))
 a = sum(map(int,input().split()[:n]))
 da = a//k
 if da>=d:
  print(d)
 else:
  print(da)


# cook your dish here
xx= int(input(''))
for j in range (xx):
 a,b,c=list(map(int,input('').split()))
 x=list(map(int,input('').split()))
 t=0
 k=0
 z=0
 for i in x:
  t=t+(i+k)//b
  k=(i+k)%b
  if t>c:
   z=1
   print(c)
   break
 if z==0:
  print(t)

# cook your dish here
xx= int(input(''))
for j in range (xx):
 a,b,c=list(map(int,input('').split()))
 x=list(map(int,input('').split()))
 t=0
 k=0
 z=0
 for i in x:
  t=t+(i+k)//b
  k=k+i%b
  if t>=c:
   z=1
   print(c)
   break
 if z==0:
  print(t)

# cook your dish here
t=int(input())
for _ in range(t):
 n,k,d=list(map(int,input().split()))
 a=list(map(int,input().split()))
 res=sum(a)//k
 if res>d:
  print(d)
 else:
  print(res)


# cook your dish here
k=int(input())
for j in range(k):
 a,b,c=list(map(int,input().split()))
 l=[]
 l=list(map(int,input().split()))
 s=sum(l)
 if(s<b):
  print("0")
 else:
  d=int(s/b)
  if(d<c):
   print(d)
  else:
   print(c)
  
 
 
  


# cook your dish here
t=int(input())
while t>0 :
 a=list(map(int,input().rstrip().split()))
 n=a[0]
 k=a[1]
 d=a[2]
 a1=list(map(int,input().rstrip().split()))
 x=sum(a1)//k 
 if x<=d:
  print(x)
 else:
  print(d)
 t=t-1


# cook your dish here
for t in range(int(input())):
 n, k, d = list(map(int, input().split()))
 problems = list(map(int, input().split()))
 sum = day = 0
 for i in problems:
  sum += i

 contest = sum // k
 if contest == 0:
  print(0)
 elif contest > d:
  print(d)
 else:
  print(contest)


# cook your dish here
t = int(input())
for _ in range(t):
 n,k,d = map(int,input().split())
 a = list(map(int,input().split()))
 total = sum(a)
 contests = total//k
 if(contests<=d):
  ans = contests
 else:
  ans = d
 print(ans)

for a in range(int(input())):
 n,k,d=map(int,input().split())
 q=map(int,input().split())
 problem=sum(q)
 days=problem//k
 if problem<k:
  print(0)
 elif days<=d:
  print(days)
 else:
  print(d)

for _ in range(int(input())):
 n,k,d = map(int,input().split())
 a = list(map(int,input().split()))
 s = sum(a)
 if s//k<d:
  print(s//k)
 else:
  print(d)

# cook your dish here
for _ in range(int(input())):
 n,k,d = [int(x) for x in input().split()]
 A = [int(x) for x in input().split()]
 t = sum(A)
 if(t<k):
  print(0)
 else:
  res = t//k
  print(min(res,d))

# cook your dish here
t=int(input())
for i in range(t):
 n,k,d=map(int,input().split())
 arr=list(map(int,input().split()))
 s=sum(arr)
 c=s//k
 if c>=d:
  print(d)
 else:
  print(c)

testc=int(input())
for i in range(testc):
 a,b,c=input().split()
 A=int(a)
 B=int(b)
 C=int(c)
 lis=list(map(int,input().split()))
 s=sum(lis)
 ans=s//B
 if(ans>C):
  print(C)
 else:
  print(ans)


import math
t = int(input())
for _ in range(t):
 n, k, d = list(map(int, input().split()))
 total_prob = sum(list(map(int, input().split())))
 nd = math.floor(total_prob / k)
 if total_prob < k:
  print(0)
 else:
  if nd < d:
   print(nd)
  else:
   print(d) 


import math
t = int(input())
for _ in range(t):
 n, k, d = list(map(int, input().split()))
 total_prob = sum(list(map(int, input().split())))
 nd = math.floor(total_prob / k)
 if total_prob < k:
  print(0)
 else:
  if nd < d:
   print(nd)
  else:
   print(d) 


# cook your dish here
t=int(input())
for i in range(t):
 n,k,d=map(int,input().split())
 if(n==1):
  summ=int(input())
 else:
  a=[]
  a=list(map(int,input().strip().split()))[:n]
  summ=sum(a)
  
 tot=summ//k
 print(min(d,tot))

# cook your dish here
t=int(input())
for i in range(t):
 n,k,d=map(int,input().split())
 if(n==1):
  summ=int(input())
 else:
  a=[]
  a=list(map(int,input().strip().split()))[:n]
  summ=sum(a)
  
 tot=summ//k
 print(min(d,tot))