There is a line with 1000 cells numbered from 1 to 1000 from left to right and N coins placed on it. Coin i is placed at cell X_{i}, and no two coins are placed at the same cell.

Bob would like to move the coins to the N leftmost cells of the line. To do this, he is allowed to take a coin from any cell T and move it to cell T-j, where j is an integer between 1 and K, inclusive. This action is possible only if:
cell T-j actually exists and doesn't contain a coin;
each of the cells T-j+1, ..., T-1 contains a coin.
One coin movement takes exactly one second. Find the smallest time in which Bob can achieve his goal.

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

The first line of the input file contains one integer T -- the number of test cases (no more than 10). Then T test cases follow, and every test case is described by two lines: the first of them contains two integers N and K (1 ≤ N, K ≤ 1000), the second of them contains N integers X_{1}, ..., X_{N} in strictly increasing order (1 ≤ X_{i} ≤ 1000).

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

For each test case output one line containing the requested minimal time for Bob to put all the coins to the left side of the line.

----- Sample Input 1 ------ 
2
3 2
2 4 7
5 3
1 2 3 4 5
----- Sample Output 1 ------ 
5
0
----- explanation 1 ------ 
In the first example Bob can move the coin from cell 7 consequently to cells 6, 5, 3 and 1, then move the coin from cell 4 to cell 3. In the second example there is nothing to move.

Difficulty: MEDIUM_HARD
Tags: Greedy algorithms

Constructive algorithms

Ad-hoc
Skill types: Greedy algorithms

Starter code:

Solutions:
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	c = 0
	for j in range(n - 1, -1, -1):
		if j > 0:
			c += (l[j] - l[j - 1] - 1) * ((n - j - 1) // k + 1)
		else:
			c += (l[j] - 1) * ((n - j - 1) // k + 1)
	print(c)


def getnewgroup(a, index, grouplength):
	grouplength += 1
	while index != 0 and a[index - 1] + 1 == a[index]:
		grouplength += 1
		index -= 1
	return (grouplength, index)
for _ in range(int(input())):
	(N, K) = list(map(int, input().split()))
	X = list(map(int, input().split()))
	index = N
	ans = 0
	grouplength = 0
	while True:
		(grouplength, index) = getnewgroup(X, index - 1, grouplength)
		if index == 0:
			ans += (X[index] - 1) * (grouplength // K + 1 * (grouplength % K != 0))
			break
		ans += (X[index] - X[index - 1] - 1) * (grouplength // K + 1 * (grouplength % K != 0))
	print(ans)


import math
T = int(input())
for t in range(T):
	(N, K) = [int(x) for x in input().split()]
	X = [int(x) for x in input().split()]
	X.reverse()
	group = 1
	count = 0
	head = X[0]
	i = 1
	for i in range(1, len(X)):
		if head - 1 == X[i]:
			pass
		else:
			count += math.ceil(group / K) * (head - X[i] - 1)
		head = X[i]
		group += 1
	count += math.ceil(group / K) * (X[-1] - 1)
	print(count)


from sys import stdin, stdout
import math
from collections import Counter, defaultdict
input = stdin.readline
t = int(input().strip())
for _ in range(t):
	(n, k) = list(map(int, input().strip().split()))
	arr = list(map(int, input().strip().split()))
	bits = [0 for i in range(1001)]
	for index in arr:
		bits[index] = 1
	bits = bits[::-1]
	(ones, zeros) = ([], [])
	(cnt1, cnt2) = (0, 0)
	for i in range(bits.index(1), 1000 + 1):
		if bits[i]:
			cnt1 += 1
		else:
			if cnt1 > 0:
				ones.append(cnt1)
			cnt1 = 0
	bits[1000] = 1
	for i in range(bits.index(1), 1000 + 1):
		if not bits[i]:
			cnt2 += 1
		else:
			if cnt2 > 0:
				zeros.append(cnt2)
			cnt2 = 0
	if len(ones) != len(zeros):
		zeros.append(0)
	ans = 0
	sumi = 0
	for i in range(len(ones)):
		sumi += ones[i]
		ans += math.ceil(sumi / k) * zeros[i]
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	x = list(map(int, input().split()))
	res = 0
	for i in range(n - 1, -1, -1):
		if i > 0:
			res += (x[i] - x[i - 1] - 1) * ((n - i - 1) // k + 1)
		else:
			res += (x[i] - 1) * ((n - i - 1) // k + 1)
	print(res)


import math

def solve():
	(N, K) = [int(x) for x in input().split()]
	X = [int(x) for x in input().split()]
	X.reverse()
	group = 1
	count = 0
	head = X[0]
	i = 1
	for i in range(1, len(X)):
		if head - 1 == X[i]:
			pass
		else:
			count += math.ceil(group / K) * (head - X[i] - 1)
		head = X[i]
		group += 1
	count += math.ceil(group / K) * (X[-1] - 1)
	print(count)
for _ in range(int(input())):
	solve()


a = int(input())
for i in range(a):
	(N, K) = map(int, input().split())
	X = list(map(int, input().split()))
	if X[N - 1] == N:
		print(0)
	else:
		x = 0
		r = 1
		for j in range(N - 1, 0, -1):
			if r % K != 0:
				x += (r // K + 1) * (X[j] - X[j - 1] - 1)
			else:
				x += int(r / K) * (X[j] - X[j - 1] - 1)
			r += 1
		if N % K != 0:
			x += (N // K + 1) * (X[0] - 1)
		else:
			x += N // K * (X[0] - 1)
		print(x)