Chef published a blog post, and is now receiving many queries about it. On day $i$, he receives $Q_i$ queries. But Chef can answer at most $k$ queries in a single day. 
Chef always answers the maximum number of questions that he can on any given day (note however that this cannot be more than $k$). The remaining questions (if any) will be carried over to the next day.
Fortunately, after $n$ days, the queries have stopped. Chef would like to know the first day during which he has some free time, i.e. the first day when he answered less than $k$ questions. 

-----Input:-----
- First line will contain $T$, the number of testcases. Then the testcases follow.
- The first line of each testcase contains two space separated integers $n$ and $k$.
- The second line of each testcase contains $n$ space separated integers, namely $Q_1, Q_2, ... Q_n$.

-----Output:-----
For each testcase, output in a single line the first day during which chef answers less than $k$ questions. 

-----Constraints-----
- $1 \leq T \leq 10^5$
- $1 \leq $ sum of $n$ over all testcases $ \leq 10^5$
- $1 \leq k \leq 10^8$
- $0 \leq Q_i \leq 10^8$

-----Subtasks-----
- Subtask 1 - 20% points - Sum of $Q_i$ over all testcases and days $\leq 3 . 10^6$
- Subtask 2 - 80% points - Original constraints

-----Sample Input:-----
2 
6 5 
10 5 5 3 2 1 
1 1
100

-----Sample Output:-----
6
101

-----Explanation:-----
Test Case 1
On the first day, chef answers 5 questions and leaves the remaining 5 (out of the 10) for the future days.
On the second day, chef has 10 questions waiting to be answered (5 received on the second day and 5 unanswered questions from day 1). Chef answers 5 of these questions and leaves the remaining 5 for the future.
On the third day, chef has 10 questions waiting to be answered (5 received on the third day and 5 unanswered questions from earlier). Chef answers 5 of these questions and leaves the remaining 5 for later.
On the fourth day, chef has 8 questions waiting to be answered (3 received on the fourth day and 5 unanswered questions from earlier). Chef answers 5 of these questions and leaves the remaining 3 for later.
On the fifth day, chef has 5 questions waiting to be answered (2 received on the fifth day and 3 unanswered questions from earlier). Chef answers all 5 of these questions.
On the sixth day, chef has 1 question, which he answers. This is the first day he answers less than 5 questions, and so the answer is 6.
Test Case 2
Chef answers 1 question a day for the first 100 days. On day 101, he is free.

Difficulty: interview

Starter code:

Solutions:
# cook your dish here

t=int(input())
while(t):
 t=t-1
 n,k=list(map(int,input().split()))
 q=list(map(int,input().split()))
 days,rem=0,0
 for i in range(n):
  rem+=q[i]
  if(rem>=k):
   rem-=k
  else:
   days=i+1
   break
  days+=1
 if(rem>=k):
  days+=(rem//k)+1
 print(days)


# cook your dish here
try:
 t=int(input())
 while(t):
  t=t-1
  n,k=map(int,input().split())
  q=list(map(int,input().split()))
  days,rem=0,0
  for i in range(n):
   rem+=q[i]
   if(rem>=k):
    rem-=k
   else:
    days=i+1
    break
   days+=1
  if(rem>=k):
   days+=(rem//k)+1
  print(days)
except:
 pass

def calFirstFreeDay(r, k, count):
 if((r-k)<k):
  print(count+2)
 else:
  calFirstFreeDay(r-k, k, count+1)
 

T = int(input())
for i in range(0, T):
 list = input().split()
 n = int(list[0])
 k = int(list[1])
  
 pq = 0
 outputDone=False;
 arr = input().split()
 if(n==1):
  print((int(int(arr[0])/k))+1)
  outputDone = True
 if(not outputDone):
  for j in range(0, n):
   q = int(arr[j])
   if((q+pq)<k):
    print((j+1));
    outputDone = True;
    break;
   else:
    pq = (q+pq)-k;
 if(not outputDone):
  calFirstFreeDay(pq, k, n)


def calFirstFreeDay(r, k, count):
 if((r-k)<k):
  print(count+2)
 else:
  calFirstFreeDay(r-k, k, count+1)
 

T = int(input())
for i in range(0, T):
 list = input().split()
 n = int(list[0])
 k = int(list[1])
 pq = 0
 outputDone=False;
 arr = input().split()
 for j in range(0, n):
  q = int(arr[j])
  if((q+pq)<k):
   print((j+1));
   outputDone = True;
   break;
  else:
   pq = (q+pq)-k;
 if(not outputDone):
  calFirstFreeDay(pq, k, n)


def solve(n, k, q):
 leftq = 0
 for i in range(n):
  leftq = leftq + q[i]
  if leftq < k:
   return i+1
  leftq = leftq - k
 
 return n + leftq//k + 1

t = int(input())

for _ in range(t):
 n, k = list(map(int , input().split()))
 queries = list(map(int , input().split()))
 print( solve(n, k, queries))
 


# cook your dish here
t=int(input())
#print(t)
for _ in range(t):
 #print(t)
 p = list(map(int, input().split()))
 n = p[0]
 k = p[1]
 l = list(map(int, input().split()))
 #print(l)
 s=0
 f=1
 for i in range(0,n):
  s += l[i]
  if(s<k):
   print(i+1)
   f=0
   break
  s = s-k
 
 if(f):
  print( sum(l)//k + 1)


try:
 t = int(input())
 for _ in range(t):
  n, k = map(int, input().split())
  qArr = list(map(int, input().split()))
  res = (sum(qArr)//k) + 1
  print(res)
except:
 pass

for i in range(int(input())):
 n,k=list(map(int,input().split()))
 q=[int(z) for z in input().split()]
 carry,flag=0,0
 for i in range(n):
  if q[i]+carry>=k:
   carry+=q[i]-k
  else:
   flag=1
   print(i+1)
   break
 if carry>0 and flag!=1:
  print(carry//k +1+n)
 elif carry==0 and flag!=1:
  print(n+1)
   


for i in range(int(input())):
 n,k=list(map(int,input().split()))
 q=[int(z) for z in input().split()]
 count=n-1
 for i in range(n-1):
  if q[i]>k:
   q[i+1]+=q[i]-k
 if q[n-1]<=k:
  count+=1
 else:
  count+=(q[n-1]//k)+1
 print(count)
   


for _ in range(int(input())):
 n, k = list(map(int, input().split()))
 arr = list(map(int, input().split()))
 left = 0
 total_q = 0
 flag = 0
 for i in range(n):
  total_q += arr[i]
  if total_q < k:
   flag= 1
   break
  total_q = total_q - k
 left = total_q

 if flag:
  print(i+1)
 else:
  if not left:
   print(n)
  else:
   print(n + int(left / k) + 1)


for _ in range(int(input())):
 n, k = list(map(int, input().split()))
 arr = list(map(int, input().split()))
 left = 0
 total_q = 0

 for i in range(n):
  total_q += arr[i]
  total_q = total_q - k if total_q - k > 0 else 0
 left = total_q

 if not left:
  print(n)
 else:
  print(n + int(left / k) + 1)


for _ in range(int(input())):
 n, k = list(map(int, input().split()))
 arr = list(map(int, input().split()))
 left = 0
 total_q = 0

 for i in range(n-1):
  total_q += int(arr[i])
  total_q = total_q - k if total_q - k > 0 else 0
 left = total_q

 left += arr[n-1]
 if left < k:
  print(n)
 elif left == k:
  print(n + 1)
 else:
  left = left - k
  print(n+int(left/k)+1)


for i in range(int(input())):
 n, k = map(int, input().split())
 arr = list(map(int, input().split()))
 s = sum(arr)
 print(max(int(s/k)+1, n))

for _ in range(int(input())):
 i=0
 n,k=map(int,input().split())
 l=list(map(int,input().split()))
 so=l[i]
 result=sum(l)
 r=result//k
 if(r<=k):
  print(r+1)
 else:
  print(r+k//so+1)

for _ in range(int(input())):
 n,k=map(int,input().split())
 l=list(map(int,input().split()))
 result=sum(l)
 r=result//k
 print(r+1)

# cook your dish here
t = int(input())
while(t > 0):
 n,k = map(int,input().split())
 q = [int(x) for x in input().split()]
 carry = 0
 flag = 0
 for i in range(n):
  if(q[i]+carry>=k):
   carry = q[i] + carry - k
  else:
   flag = 1
   print(i+1)
   break
 if(carry > 0 and flag != 1):
  rem = carry//k + 1 + n
  print(rem)
 elif(carry == 0 and flag != 1):
  print(n+1)
 t -= 1

# cook your dish here
t = int(input())
while(t > 0):
 n,k = map(int,input().split())
 q = [int(x) for x in input().split()]
 carry = 0
 for i in range(n):
  if(q[i]+carry>=k):
   carry = q[i] + carry - k
  else:
   print(i+1)
   break
 if(carry > 0 and k != 0):
  rem = carry//k + 1 + n
  print(rem)
 elif(carry == 0):
  print(n+1)
 t -= 1

# cook your dish here
t = int(input())
while(t > 0):
 n,k = map(int,input().split())
 q = [int(x) for x in input().split()]
 carry = 0
 for i in range(n):
  if(q[i]+carry>=k):
   carry = q[i] + carry - k
  else:
   print(i+1)
   break
 if(carry > 0):
  rem = carry//k + 1 + n
  print(rem)
 elif(carry == 0):
  print(n+1)
 t -= 1

# cook your dish here
t = int(input())
while(t > 0):
 n,k = map(int,input().split())
 q = [int(x) for x in input().split()]
 carry = 0
 for i in range(n):
  if(q[i]+carry>=k):
   carry = q[i] + carry - k
  elif(q[i]+carry<k):
   print(i+1)
   break
  else:
   print(i+1)
   break
 if(carry > 0):
  rem = carry//k + 1 + n
  print(rem)
 t -= 1

# cook your dish here
t = int(input())
while(t > 0):
 n,k = map(int,input().split())
 q = [int(x) for x in input().split()]
 carry = 0
 for i in range(n):
  if(q[i]+carry>=k):
   carry = q[i] + carry - k
  else:
   print(i+1)
   break
 if(carry > 0):
  rem = carry//k + 1 + n
  print(rem)
 t -= 1

t=int(eval(input('')))
for i in range(t):
 n, k = [int(n) for n in input(" ").split()]
 lst = list(map(int, input().split()))
 j=0
 leftover=0
 ans=0
 for i in range(n):
  j=lst[i]+leftover
  leftover=j-k
  if(j<k):
   ans=i+1 
   break
 if(leftover>=0):
  ans=n+(leftover//k)+1 
 print(ans)


t=int(input())
for each in range(t):
 n,k=map(int,input().split())
 q=list(map(int,input().split()))
 i=0
 while True:
  if i<n:
   if i==0:
    if q[i]<k:
     print(i+1)
     break
    r=q[i]-k
    i+=1
   else:
    if (r+q[i])<k:
     print(i+1)
     break
    r=(r+q[i])-k
    i=i+1 
  else:
   print(i+(r//k)+1)
   break

# sai ram
for _ in range(int(input())):
 n,k=[int(x) for x in input().split()]
 q=[int(x) for x in input().split()]
 
 
 print((sum(q)//k)+1)