Read problems statements in Mandarin Chinese  and Russian. 
Some chefs go for a tour lasting N days. They take packages of bread for food. Each package has K pieces of breads. On the i^{th} day, they eat A_{i} pieces of bread.
Unfortunately, chefs are very lazy people, and they always forget to close the package of breads, so each day the last piece of bread becomes exposed to mold (a fungus), and is no longer suitable for eating. Such a bad piece is not eaten, and is instead thrown away. 
Let us take an example. If K = 4 and N = 3, then A = {3, 1, 2}. Chefs have packages of bread each having 4 pieces of bread, and their travel lasts 3 days. In the first day, they must eat 3 pieces of bread. So they open new package of bread and eat 3 pieces. They forget to close the package, so the 4^{th} piece becomes bad. In the next day, they want to eat one piece of bread. And in the first package we don't have any good pieces of bread left, so they open a new package of bread and eat one piece from that. On the 3^{rd} day, they want to eat 2 pieces of bread. In the second package, we have three pieces, and one of them is bad; so we have 2 good pieces. They eat 2 pieces from this package. So they must buy 2 packages of bread.
Please help chefs in finding out the minimum number of packages of breads they should take with them on the tour.

------ Input ------ 

The first line of input contains a single integer T denoting the number of test cases.
The first line of each test contains two space separated integers N and K.
The next line of each test case contains N space separated integers denoting the number of pieces of bread the chefs want to eat each day.

------ Output ------ 

For each of the T test cases, output a single line - minimum number of packages of bread the chefs should take.
------ 
------ Constraints -----
$1 ≤ T ≤ 10$
 
Subtask 1: 15 points
$1 ≤ N ≤ 100$
$1 ≤ K ≤ 100$
$1 ≤ A_{i} ≤ 100$
 
Subtask 2: 25 points
$1 ≤ N ≤ 10^{5}$
$1 ≤ K ≤ 10^{6}$
$1 ≤ A_{i} ≤ 10^{6}$
 
Subtask 3: 60 points
$1 ≤ N ≤ 10^{5}$
$1 ≤ K ≤ 10^{11}$
$1 ≤ A_{i} ≤ 10^{6}$
 
----- Sample Input 1 ------ 
3
3 4
3 1 2
1 1
1
2 4
8 8
----- Sample Output 1 ------ 
2
1
4
----- explanation 1 ------ 

Test case 1 has already been explained in the statement.

In test case 2, we have one day tour and packages with one piece each. In the first day, we have to eat one piece of bread, so we open a package and eat one piece. Tour ended, and our answer is 1.

In test case 3, we have a two days tour, and packages with 4 pieces of bread each. In the first day, we have to eat 8 pieces. We need to open two packages and eat all the pieces. In the second day, we have to eat 8 pieces again. We open two packages and eat all pieces. Tour ended. Answer is 4.

Difficulty: MEDIUM
Tags: Mathematics

Starter code:

Solutions:
import sys
from itertools import *
from pprint import pprint

def solve():
	(N, K) = tuple((int(x) for x in sys.stdin.readline().split()))
	AS = tuple((int(x) for x in sys.stdin.readline().split()))
	assert len(AS) == N
	total = 0
	left = 0
	for a in AS:
		if left > 0:
			left -= 1
		total += a // K
		a = a % K
		while left < a:
			a -= left
			left = K
			total += 1
		left -= a
	return total

def perr(*ns):
	pprint(ns, stream=sys.stderr)
for _ in range(int(sys.stdin.readline())):
	print(solve())


import math
for t in range(int(input())):
	temp = list(map(int, input().split()))
	n = temp[0]
	k = temp[1]
	a = list(map(int, input().split()))
	re = 0
	count = 0
	for i in range(n):
		if re > 0:
			re -= 1
		if re >= a[i]:
			re -= a[i]
			continue
		else:
			a[i] -= re
			re = 0
			need = math.ceil(a[i] / k)
			count += need
			re = need * k
			re -= a[i]
			continue
	print(count)


from math import ceil
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	r = 0
	ans = 0
	for j in range(n):
		if l[j] == k:
			ans += 1
			continue
		else:
			if r >= l[j]:
				r -= l[j]
			else:
				b = ceil((l[j] - r) / k)
				ans += b
				r = k * b - (l[j] - r)
			if r > 0:
				r -= 1
	print(ans)


t = int(input())
for j in range(t):
	nk = [int(word) for word in input().split() if word.isdigit()]
	eat = [int(word) for word in input().split() if word.isdigit()]
	pieces = 0
	for i in eat:
		pieces += i
		if pieces % nk[1] != 0:
			pieces += 1
	if pieces % nk[1] == 0:
		print(pieces // nk[1])
	else:
		print(pieces // nk[1] + 1)


T = int(input())
while T:
	(N, K) = [int(x) for x in input().split()]
	A = [int(x) for x in input().split()]
	sum = 0
	left = 0
	for x in A:
		sum += x
		if x <= left:
			left -= x
		elif (x - left) % K:
			left = K - (x - left) % K
		else:
			left = 0
		if left:
			left -= 1
			sum += 1
	if sum % K:
		print(sum // K + 1)
	else:
		print(sum // K)
	T -= 1


def main():
	T = int(input())
	for t in range(T):
		(N, K) = [int(x) for x in input().split()]
		A = [int(x) for x in input().split()]
		ans = 0
		remaining_from_last = 0
		for x in A:
			if remaining_from_last > 0:
				m = min(remaining_from_last, x)
				remaining_from_last -= m
				x -= m
			if x == 0:
				if remaining_from_last > 0:
					remaining_from_last -= 1
				continue
			full_loaves_used = x // K
			ans += full_loaves_used
			x -= full_loaves_used * K
			if x == 0:
				continue
			remaining_from_last = K - x - 1
			ans += 1
		print(ans)
main()


import math
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	su = 0
	for i in range(n):
		su += a[i]
		if su % k != 0:
			su += 1
	print(math.ceil(su / k))


import math
a = int(input())
while a > 0:
	a -= 1
	b = input()
	(n, k) = [int(n) for n in b.split()]
	c1 = input()
	c = [int(n) for n in c1.split()]
	(q, r) = (0, 0)
	for i in range(n - 1):
		q += c[i]
		if q % k != 0:
			q += 1
	q += c[n - 1]
	r = q / k
	r = math.ceil(r)
	print(r)


for q in range(int(input())):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	(extra, cnt) = (0, 0)
	for i in range(len(a)):
		temp = min(extra, a[i])
		extra -= temp
		a[i] -= temp
		cnt += a[i] // m
		x = a[i] % m
		if x > 0:
			cnt += 1
			extra += m - x
		if extra > 0:
			extra -= 1
	print(cnt)


t = int(input())
for i in range(t):
	(n, k) = input().split()
	(n, k) = (int(n), int(k))
	a = input().split()
	a = list(map(int, a))
	left = 0
	count = 0
	for i in range(n):
		if left < a[i]:
			p = int((a[i] - left) / k)
			q = p * k
			if a[i] - left > q:
				p = p + 1
			count += p
			left = p * k - a[i] + left
			if left > 0:
				left = left - 1
		elif a[i] < left:
			left = left - a[i] - 1
		elif a[i] == left:
			left = 0
	print(count)


t = int(input())
for j in range(t):
	l = input().split()
	n = int(l[0])
	k = int(l[1])
	ar = list(map(int, input().split()))
	count = 0
	t = k
	for i in range(n):
		while ar[i] != 0:
			if ar[i] >= t:
				if t == k:
					count += ar[i] // t
					ar[i] = ar[i] % t
					t = k
				else:
					ar[i] -= t
					t = k
					count += 1
			else:
				t = t - ar[i]
				ar[i] = 0
				t = t - 1
				if t <= 0:
					count += 1
					t = k
				elif t > 0 and i == n - 1:
					count += 1
	print(count)


from math import ceil
t = int(input())
for tc in range(0, t):
	(n, k) = [int(i) for i in input().split()]
	a = [int(i) for i in input().split()]
	cur = 0
	ans = 0
	for i in range(0, n):
		if a[i] < cur:
			cur = cur - a[i]
		else:
			x = ceil((a[i] - cur) / k)
			ans = ans + int(x)
			cur = cur + (x * k - a[i])
		if cur > 0:
			cur = cur - 1
	print(ans)


from sys import stdin
T = int(stdin.readline().strip())
while T > 0:
	[N, K] = [int(n) for n in stdin.readline().strip().split()]
	A = [int(n) for n in stdin.readline().strip().split()]
	remaining = K
	count = 0
	for elem in A:
		if remaining == K:
			count += elem // K
			elem %= K
			if elem:
				remaining = remaining - elem - 1
		elif elem > remaining:
			elem -= remaining
			remaining = K
			count += elem // K + 1
			elem %= K
			if elem:
				remaining = remaining - elem - 1
		else:
			remaining -= elem
			if remaining == 0:
				remaining = K
				count += 1
			else:
				remaining -= 1
	if remaining != K:
		count += 1
	print(count)
	T -= 1


t = int(input())
for _ in range(t):
	(N, K) = map(int, input().split())
	arr = list(map(int, input().split()))
	total = 0
	remaining = 0
	i = 0
	spare = 0
	while i < N:
		total = total + arr[i]
		if total % K != 0:
			total = total + 1
		i = i + 1
	if total % K == 0:
		print(total // K)
	else:
		print(total // K + 1)


def cal(a, n, k):
	(now, nk) = (0, k)
	for i in range(n):
		tmp = a[i]
		if nk != k:
			if tmp <= nk:
				nk -= tmp
				nk -= 1
				tmp = 0
				if nk <= 0:
					nk = k
					now += 1
			else:
				tmp -= nk
				nk = k
				now += 1
		if tmp != 0:
			nd = tmp // k
			now += nd
			tmp %= k
		if tmp != 0:
			nk -= tmp
			nk -= 1
			tmp = 0
	if nk != k:
		now = now + 1
	return now
times = int(input())
while times > 0:
	times -= 1
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	(l, r, mid) = (0, 100000000000, 0)
	ans = cal(a, n, k)
	print(ans)


cas = int(input())
for i in range(cas):
	(n, k) = map(int, input().split())
	a = map(int, input().split())
	last = co = 0
	for i in a:
		s = i
		if last >= s:
			last = last - s
			s = 0
		elif last < s:
			s -= last
			last = 0
		co += int(s / k)
		s = s % k
		if s >= 1:
			co += 1
			last = k - s
		if last >= 1:
			last -= 1
	print(int(co))


t = int(input())
while t > 0:
	(n, k) = tuple([int(x) for x in input().split()])
	ans = 0
	left = 1
	for i in input().split():
		x = int(i)
		if left > 0:
			left -= 1
		nu_pkgs = (x - left) // k
		rem = (x - left) % k
		left = 0
		if rem != 0:
			nu_pkgs += 1
			left = k - rem
		ans += nu_pkgs
	print(ans)
	t -= 1


t = int(input())
for i in range(t):
	s = input().split()
	n = int(s[0])
	k = int(s[1])
	count = 0
	s = input().split()
	d = int(s[0]) / k
	if d.is_integer():
		count += d
		x = d * k - int(s[0])
	else:
		count += int(d) + 1
		x = (int(d) + 1) * k - int(s[0])
	l = x
	j = 1
	while j < n:
		if l > 0:
			l = l - 1
		if l >= int(s[j]):
			l = l - int(s[j])
			j += 1
			continue
		l = int(s[j]) - l
		d = l / k
		if d.is_integer():
			count += d
			l = d * k - l
		else:
			count += int(d) + 1
			l = (int(d) + 1) * k - l
		j += 1
	print(int(count))


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	s = 0
	for x in l:
		s += x
		if s % k != 0:
			s += 1
	if s % k == 0:
		print(int(s / k))
	else:
		print(int(s / k + 1))


import sys

def solve(n, k, A):
	(bags, resto) = (0, 0)
	for value in A:
		if resto >= value:
			resto -= value + 1
			resto = max(resto, 0)
			continue
		value -= resto
		resto = 0
		bags += value // k
		if value % k != 0:
			bags += 1
			resto = k - value % k - 1
	return bags
casos = int(input())
for i in range(casos):
	line = input()
	(n, k) = tuple([int(x) for x in line.split()])
	line = input()
	A = [int(x) for x in line.split()]
	answer = solve(n, k, A)
	print(answer)


from math import ceil
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	l = [int(x) for x in input().split()]
	remBread = 0
	ans = 0
	for i in range(n):
		if l[i] == k:
			ans += 1
			continue
		else:
			if remBread >= l[i]:
				remBread -= l[i]
			else:
				reqBreadPacket = ceil((l[i] - remBread) / k)
				ans += reqBreadPacket
				remBread = k * reqBreadPacket - (l[i] - remBread)
			if remBread > 0:
				remBread -= 1
	print(ans)


def solve(K, a):
	fromYest = 0
	toBuy = 0
	for v in a:
		eatFromTest = min(v, fromYest)
		v -= eatFromTest
		fromYest -= eatFromTest
		(q, r) = divmod(v, K)
		toBuy += q
		if r > 0:
			toBuy += 1
			fromYest = K - r
		if fromYest > 0:
			fromYest -= 1
	return toBuy
T = int(input())
for _ in range(T):
	(_, K) = map(int, input().split())
	a = list(map(int, input().split()))
	print(solve(K, a))


T = int(input())
for i in range(T):
	(N, K) = map(int, input().split())
	x = list(map(int, input().split()))
	ans = 0
	bag = 0
	for j in x:
		if bag != 0:
			if j <= bag:
				bag = bag - j
				if bag != 0:
					bag -= 1
				continue
			else:
				j = j - bag
				bag = 0
		if j <= K:
			ans += 1
			bag = K - j
			if bag != 0:
				bag -= 1
		else:
			if j % K == 0:
				p = j // K
			else:
				p = j // K + 1
			ans = ans + p
			bag = p * K - j
			if bag != 0:
				bag -= 1
	print(ans)


import math
tests = int(input())
for i in range(tests):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	ans = 0
	for j in arr:
		if ans % k != 0:
			ans += 1
		ans += j
	print(math.ceil(ans / k))


T = int(input())
for ti in range(T):
	(n, k) = map(int, input().split())
	A = list(map(int, input().split()))
	res = 0
	nump = 0
	for ai in range(len(A)):
		if A[ai] >= res:
			fd = A[ai] - res
			pi = fd // k
			nump += pi
			if pi > 0:
				if fd % k == 0:
					res = 0
				else:
					res = k - fd % k - 1
					nump += 1
			elif fd % k == 0:
				res = 0
			else:
				res = k - fd - 1
				nump += 1
		else:
			fd = res - A[ai]
			res = fd - 1
	print(nump)


import math
t = int(input())
for ele in range(t):
	(n, k) = input().split()
	(n, k) = (int(n), int(k))
	arr = input().split()
	arr = [int(i) for i in arr]
	(packets, leftOver) = (0, 0)
	for i in range(n):
		today = arr[i]
		if leftOver > today:
			leftOver = leftOver - today - 1
		elif leftOver == today:
			leftOver = 0
		else:
			today -= leftOver
			packets += math.ceil(today / k)
			leftOver = k - today % k - 1 if today % k != 0 else 0
	print(packets)


from math import ceil
tests = int(input())
for t in range(tests):
	(n, k) = [int(i) for i in input().split()]
	a = [int(i) for i in input().split()]
	packages = 1
	remaining = k
	for ai in a:
		if ai > remaining:
			ai -= remaining
			toopen = ceil(ai / k)
			packages += toopen
			remaining = toopen * k - ai - 1
		else:
			remaining -= ai + 1
		remaining = max(remaining, 0)
	print(packages)


import math
t = int(input())
while t > 0:
	x = input().split()
	n = int(x[0])
	k = int(x[1])
	x = input().split()
	a = []
	for i in range(n):
		a.append(int(x[i]))
	remain = 0
	count = 0
	for i in range(n):
		if remain > a[i]:
			remain = remain - a[i]
		else:
			a[i] = a[i] - remain
			remain = 0
			if a[i] > 0:
				c = int(math.ceil(a[i] / k))
				count = count + c
				extra = int(a[i] % k)
				if extra > 0:
					remain = k - extra
		if remain > 0:
			remain = remain - 1
	print(count)
	t = t - 1


t = int(input())
while t:
	t -= 1
	(n, k) = input().split()
	n = int(n)
	k = int(k)
	a = input().split()
	ans = 0
	for i in range(n):
		if ans % k != 0:
			ans += 1
		ans += int(a[i])
	if ans % k == 0:
		print(ans // k)
	else:
		print(ans // k + 1)


import math
cases = int(input())
for case in range(0, cases):
	(tourDays, piecesPerPackage) = [int(x) for x in input().split()]
	dayPieces = [int(x) for x in input().split()]
	piecesNeeded = 0
	moldyPieces = 0
	for day in range(0, tourDays):
		piecesToEat = dayPieces[day]
		if piecesToEat > 0:
			piecesNeeded += piecesToEat + moldyPieces
			moldyPieces = 0
		if piecesNeeded % piecesPerPackage != 0:
			moldyPieces += 1
	packagesNeeded = math.ceil(piecesNeeded / piecesPerPackage)
	print(packagesNeeded)


import math
t = int(input())
while t > 0:
	c = 0
	(n, k) = [int(x) for x in input().split()]
	a = []
	a = [int(x) for x in input().split()]
	for i in range(len(a)):
		d = math.ceil(a[i] / k)
		c = c + d
		e = 0
		if a[i] % k != 0 and a[i] % k != k - 1:
			e = d * k - a[i] - 1
		if i != len(a) - 1:
			a[i + 1] = a[i + 1] - e
	print(c)
	t = t - 1


import math
for _ in range(int(input())):
	(days, size) = input().split()
	days = int(days)
	size = int(size)
	deList = []
	deList = input().split()
	package = 1
	liCP = size
	for day in range(days):
		check = 0
		todayPack = 0
		tbE = int(deList[day])
		if liCP < tbE:
			tbE = tbE - liCP
			liCP = 0
			check = 0
		else:
			liCP = liCP - tbE
			check = 1
		if check == 0:
			todayPack = int(math.ceil(tbE * 1.0 / size))
			liCP = todayPack * size - tbE
		if liCP > 0:
			liCP -= 1
		package += todayPack
	print(package)


t = int(input())
while t:
	t -= 1
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	x = k
	c = 0
	for i in range(n):
		if arr[i] == x - 1 or arr[i] == x:
			c += 1
			x = k
		elif arr[i] < x - 1:
			x -= arr[i] + 1
		else:
			p = arr[i] - x
			c += 1
			y = p // k
			c += y
			z = k - p % k
			if z == k:
				x = k
			elif z == 1:
				c += 1
				x = k
			else:
				x = z - 1
	if x != k:
		c += 1
	print(c)


import math
t = int(input())
for j in range(t):
	(n, k) = input().split()
	n = int(n)
	k = int(k)
	arr = input().split()
	arr = [int(i) for i in arr]
	pack = 0
	breadsleft = 0
	for i in range(n):
		new = arr[i]
		if breadsleft > new:
			breadsleft = breadsleft - new - 1
		elif breadsleft == new:
			breadsleft = 0
		else:
			new = new - breadsleft
			pack = pack + math.ceil(new / k)
			if new % k != 0:
				breadsleft = k - 1 - new % k
			else:
				breadsleft = 0
	print(pack)


import math

def main():
	t = int(input())
	for _ in range(t):
		(n, k) = map(int, input().split())
		arr = list(map(int, input().split()))
		sum = 0
		for a in arr:
			sum = sum + a
			if sum % k != 0:
				sum = sum + 1
		print(math.ceil(sum / k))
main()


t = int(input())
for it in range(t):
	(n, k) = [int(word) for word in input().split()]
	a = [int(word) for word in input().split()]
	bcum = a[0]
	for i in range(1, n):
		if bcum % k == 0:
			bcum += a[i]
		else:
			bcum += a[i] + 1
	if bcum % k == 0:
		print(bcum // k)
	else:
		print(bcum // k + 1)


import math
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	rem = 0
	packs = 0
	for i in range(n):
		if rem > 0:
			rem -= 1
		if rem > a[i]:
			rem -= a[i]
			need = 0
		else:
			need = a[i] - rem
			rem = 0
		cur = math.ceil(need / k)
		rem += max(cur * k - need, 0)
		packs += cur
	print(packs)


import math
tc = int(input())
ans = []
for i in range(tc):
	inp = input()
	N = int(inp.split()[0])
	K = int(inp.split()[1])
	brd = [int(x) for x in input().split()]
	res = 0
	nbread = 0
	for x in brd:
		if x > res:
			a = math.ceil((x - res) / K)
			res = a * K - x + res
			nbread = nbread + a
		else:
			res = res - x
		if res != 0:
			res = res - 1
	ans.append(nbread)
for i in ans:
	print(i)


import math
t = int(input())
for it in range(t):
	inp = input()
	inp = inp.rstrip(' ')
	(n, k) = map(int, inp.split(' '))
	a = input()
	a = a.rstrip(' ')
	a = list(map(int, a.split(' ')))
	rem = 0
	count = 0
	for i in range(n):
		if rem <= a[i] and rem != 0:
			a[i] = a[i] - rem
			count = count + 1
		elif rem != 0:
			rem = rem - a[i] - 1
			if rem <= 0:
				rem = 0
				count = count + 1
			continue
		if a[i] > k:
			count = count + a[i] // k
			a[i] = a[i] % k
		if a[i] != 0:
			rem = k - a[i] - 1
			if rem <= 0:
				rem = 0
				count = count + 1
		else:
			rem = 0
	if rem != 0:
		count += 1
	print(count)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	a = [int(i) for i in input().split()]
	b = 0
	for i in a:
		b += i
		if b % k == 0:
			pass
		else:
			b += 1
	if b % k == 0:
		print(b // k)
	else:
		print(b // k + 1)


from copy import deepcopy as dc
from math import ceil
tCase = int(input())
for times in range(tCase):
	(noOfDays, biscuitsInEACHPack) = [int(x) for x in input().split()]
	listOfConsumption = [int(x) for x in input().split()]
	(counter, leftOver) = (0, 0)
	for item in listOfConsumption:
		copyy = item
		if leftOver >= copyy:
			leftOver -= copyy
		else:
			if leftOver > 0:
				copyy -= leftOver
				leftOver = 0
			counter += ceil(copyy / biscuitsInEACHPack)
			leftOver = ceil(copyy / biscuitsInEACHPack) * biscuitsInEACHPack - copyy
		if leftOver > 0:
			leftOver -= 1
	print(counter)


for T in range(int(input())):
	S = input().split()
	k = int(S[1])
	left = 0
	ans = 0
	for S in input().split():
		eat = int(S)
		if left > 0:
			left -= 1
		if eat <= left:
			left -= eat
			continue
		eat -= left
		left = 0
		ans += eat // k
		if eat % k > 0:
			left = k - eat % k
			ans += 1
	print(ans)


import math
t = int(input())
while t:
	inp = input().split()
	n = int(inp[0])
	k = int(inp[1])
	(z, s, i) = (0, 0, 0)
	inp1 = input().split()
	while n:
		x = int(inp1[i])
		if z > 0:
			z -= 1
			s += 1
		else:
			pass
		if z < x:
			x1 = x
			x1 -= z
			y = math.ceil(x1 / k)
			z += k * y
			z -= x
			s += x
		else:
			z -= x
			s += x
		i += 1
		n -= 1
	print(math.ceil(s / k))
	t -= 1