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.
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()]
 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)
   
