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: UNKNOWN_DIFFICULTY

Starter code:

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


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


t = int(input())
for _ in range(t):
	p = list(map(int, input().split()))
	n = p[0]
	k = p[1]
	l = list(map(int, input().split()))
	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)
	elif not left:
		print(n)
	else:
		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)


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


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


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)