You are given a permutation$^\dagger$ $p$ of length $n$ and a positive integer $k \le n$.

In one operation, you:

Choose $k$ distinct elements $p_{i_1}, p_{i_2}, \ldots, p_{i_k}$.

Remove them and then add them sorted in increasing order to the end of the permutation.

For example, if $p = [2,5,1,3,4]$ and $k = 2$ and you choose $5$ and $3$ as the elements for the operation, then $[2, {5}, 1, {3}, 4] \rightarrow [2, 1, 4, {3},{5}]$.

Find the minimum number of operations needed to sort the permutation in increasing order. It can be proven that it is always possible to do so.

$^\dagger$ A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array), and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array).


-----Input-----

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The description of test cases follows.

The first line of each test case contains two integers $n$ and $k$ ($2 \le n \le 10^5$, $1 \le k \le n$).

The second line of each test case contains $n$ integers $p_1,p_2,\ldots, p_n$ ($1 \le p_i \le n$). It is guaranteed that $p$ is a permutation.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.


-----Output-----

For each test case output a single integer — the minimum number of operations needed to sort the permutation. It can be proven that it is always possible to do so.


-----Examples-----

Input
4
3 2
1 2 3
3 1
3 1 2
4 2
1 3 2 4
4 2
2 3 1 4
Output
0
1
1
2


-----Note-----

In the first test case, the permutation is already sorted.

In the second test case, you can choose element $3$, and the permutation will become sorted as follows: $[{3}, 1, 2] \rightarrow [1, 2, {3}]$.

In the third test case, you can choose elements $3$ and $4$, and the permutation will become sorted as follows: $[1, {3}, 2, {4}] \rightarrow [1, 2, {3},{4}]$.

In the fourth test case, it can be shown that it is impossible to sort the permutation in $1$ operation. However, if you choose elements $2$ and $1$ in the first operation, and choose elements $3$ and $4$ in the second operation, the permutation will become sorted as follows: $[{2}, 3, {1}, 4] \rightarrow [\color{blue}{3}, \color{blue}{4}, {1}, {2}] \rightarrow [1,2, \color{blue}{3}, \color{blue}{4}]$.

Source: codeforces | Difficulty: EASY
Tags: Mathematics

Greedy algorithms


Solutions:
import sys

def in_int():
	return int(sys.stdin.readline())

def in_str():
	return sys.stdin.readline().rstrip()

def in_map_int():
	return map(int, sys.stdin.readline().split())

def in_arr_int():
	return list(map(int, sys.stdin.readline().split()))

def in_arr_str():
	return sys.stdin.readline().split()

def is_prime(n):
	for i in range(2, int(n ** (1 / 2)) + 1):
		if n % i == 0:
			return True
	return False

def bin2dec(s):
	n = 0
	for i in range(len(s)):
		n += int(s[len(s) - i - 1]) * 2 ** i
	return n

def gcd(a, b):
	(a, b) = (max(a, b), min(a, b))
	while b != 0:
		(a, b) = (b, a % b)
	return a

def dec2bin(n):
	if n == 0:
		return '0'
	ans = ''
	while n > 0:
		ans += str(n % 2)
		n //= 2
	return ans[::-1]

def solve(n, k, arr):
	i = 1
	for a in arr:
		if a == i:
			i += 1
	i -= 1
	return (n - i + k - 1) // k

def main():
	t = in_int()
	for _ in range(t):
		(n, k) = in_map_int()
		arr = in_arr_int()
		print(solve(n, k, arr))
main()


from sys import stdin

def solve():
	(n, k) = map(int, stdin.readline().split())
	p = list(map(int, stdin.readline().split()))
	cur = 1
	for i in range(n):
		if p[i] == cur:
			cur += 1
	todo = n - cur + 1
	print((todo + k - 1) // k)

def main():
	t = int(stdin.readline())
	for _ in range(t):
		solve()
main()


import sys
import math

def fn(n, k, p):
	if n == 1:
		return 0
	curr_num = 1
	for item in p:
		if item == curr_num:
			curr_num += 1
	curr_num -= 1
	return math.ceil((n - curr_num) / k)
input = sys.stdin.readlines()
for i in range(int(input[0].strip('\n'))):
	(n, k) = tuple([int(x) for x in input[2 * i + 1].strip('\n').split(' ')])
	p = [int(x) for x in input[2 * i + 2].strip('\n').split(' ')]
	print(fn(n, k, p))


import sys
input = sys.stdin.readline
inp = sys.stdin.readline

def input():
	return inp().strip()

def ii():
	return int(input())

def mi():
	return map(int, input().split())

def li():
	return list(map(int, input().split()))

def solve():
	(n, k) = mi()
	arr = li()
	count = 0
	left = 1
	for curr in arr:
		if curr != left:
			count += 1
		else:
			left += 1
	if count % k == 0:
		print(count // k)
	else:
		print(count // k + 1)

def main():
	for _ in range(ii()):
		solve()
main()


import sys, math, bisect, collections, itertools, heapq
from collections import defaultdict, deque
sys.setrecursionlimit(50000)
t = int(sys.stdin.readline())
for _ in range(t):
	(n, k) = map(int, sys.stdin.readline().split())
	arr = list(map(int, sys.stdin.readline().split()))
	iterate = 1
	for i in arr:
		if i == iterate:
			iterate += 1
	ans = n - (iterate - 1)
	if ans % k == 0:
		print(ans // k)
	else:
		print(ans // k + 1)


import sys
import math
import cmath
import time
from bisect import bisect_left
start_time = time.time()

def per():
	(n, k) = map(int, inps())
	l = [int(j) for j in inps()]
	c = 1
	for i in l:
		if i == c:
			c = c + 1
	print(math.ceil((n - c + 1) / k))

def main():
	testcases = 1
	testcases = inp()
	for each_testcase in range(testcases):
		per()

def inp():
	return int(input())

def inps():
	return input().split()
ans = __debug__
if ans:
	input = sys.stdin.readline
main()


import sys
input = sys.stdin.readline
res = []
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	nownum = 1
	for i in range(n):
		if arr[i] == nownum:
			nownum += 1
	nownum -= 1
	if nownum == n:
		res.append(0)
		continue
	n -= nownum
	if n % k == 0:
		res.append(n // k)
	else:
		res.append(n // k + 1)
print('\n'.join(map(str, res)))


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	P = list(map(int, input().split()))
	temp = 1
	cnt = 0
	for i in range(n):
		if P[i] == temp:
			temp += 1
		else:
			cnt += 1
	print(cnt // k + int(cnt % k != 0))


import sys
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
test_cases = inp()
inp_arr = []
for i in range(test_cases):
	nums = inlt()
	arr = inlt()
	inp_arr.append((nums[0], nums[1], arr))

def findResult(n, k, arr):
	c = 0
	mf = 1
	n = len(arr)
	for i in arr:
		if i == mf:
			c += 1
			mf += 1
	import math
	return math.ceil((n - c) / k)
result = [findResult(n, k, arr) for (n, k, arr) in inp_arr]
for m in result:
	print(m)


import sys

def _input():
	return sys.stdin.readline().strip()

def main():
	for _ in range(int(_input())):
		(n, k) = map(int, _input().split())
		l = list(map(int, _input().split()))
		index_array = [0 for i in range(n + 1)]
		for i in range(n):
			index_array[l[i]] = i
		prev_index = index_array[1]
		x = n - 1
		for i in range(2, n + 1):
			if index_array[i] > prev_index:
				prev_index = index_array[i]
				x -= 1
			else:
				break
		if x % k == 0:
			print(x // k)
		else:
			print(x // k + 1)
main()


import sys
input = sys.stdin.readline

def readList():
	return list(map(int, input().split()))

def readInt():
	return int(input())

def readInts():
	return map(int, input().split())

def readStr():
	return input().strip()

def solve():
	(n, k) = readInts()
	arr = readList()
	idx = arr.index(1)
	ans = idx
	cnt = 0
	for i in range(idx + 1, n):
		if arr[i] == cnt + 2:
			cnt += 1
		else:
			ans += 1
	ans = ans // k + 1 if ans % k and ans else ans // k
	return ans
for _ in range(int(input())):
	print(solve())


import sys, io, os
input = sys.stdin.readline
I = lambda : list(map(int, input().split()))
(t,) = I()
for _ in range(t):
	(n, k) = I()
	p = I()
	target = 1
	steps = 0
	for x in p:
		if target == x:
			target += 1
		else:
			steps += 1
	if steps // k == steps / k:
		print(steps // k)
	else:
		print(steps // k + 1)


import sys
import math
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	(*p,) = map(int, input().split())
	target = 1
	re = 0
	for e in p:
		if e == target:
			target += 1
		else:
			re += 1
	print(math.ceil(re / k))


import sys
import math
t = int(sys.stdin.readline())
for i in range(t):
	(n, k) = map(int, sys.stdin.readline().split())
	p = list(map(int, sys.stdin.readline().split()))
	st = 0
	for j in range(n):
		if p[j] == st + 1:
			st += 1
	numb = n - st
	ans = math.ceil(numb / k)
	sys.stdout.write(str(ans) + '\n')


import sys
import itertools
import bisect
import math
import collections
t = int(sys.stdin.readline())
while t >= 1:
	(n, k) = map(int, sys.stdin.readline().split())
	a = list(map(int, sys.stdin.readline().split()))
	check = 1
	count = 0
	for i in range(len(a)):
		if a[i] == check:
			check += 1
		else:
			count += 1
	ans = math.ceil(count / k)
	sys.stdout.write(str(ans))
	sys.stdout.write('\n')
	t -= 1


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	p = list(map(int, input().split()))
	c = 1
	for i in range(n):
		if p[i] == c:
			c += 1
	print((n - c + k) // k)


import sys
input = sys.stdin.readline
for tc in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	lis = 0
	for x in a:
		if x == lis + 1:
			lis += 1
	print((n - lis + k - 1) // k)


import sys
for i in range(int(sys.stdin.readline())):
	(n, k) = map(int, sys.stdin.readline().split())
	ls = [int(a) for a in sys.stdin.readline().split()]
	m = 100001
	c = 1
	for ite in range(n):
		if c == ls[ite]:
			if c + 1 == m:
				break
			c += 1
			continue
		if m > ls[ite]:
			m = ls[ite]
	if m == 100001:
		print('0')
		continue
	print((n - c + k - 1) // k)


import math
t = int(input())
result_list = []
for i in range(t):
	(n, k) = map(int, input().split())
	n_list = list(map(int, input().split()))
	s1 = 1
	for i in range(n):
		if n_list[i] == s1:
			s1 += 1
	result_list.append(math.floor((n - s1 + k) / k))
for i in result_list:
	print(i)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	d = [0] * n
	c = 1
	for i in range(n):
		if a[i] == c:
			c += 1
	c -= 1
	if (n - c) % k == 0:
		print((n - c) // k)
	else:
		print(1 + (n - c) // k)


import math
import sys
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
for _ in range(int(input())):
	(n, k) = invr()
	arr = inlt()
	data = {}
	for i in range(n):
		data[arr[i]] = i
	count = 1
	check = data[1]
	tell = 2
	while True:
		if tell in data and data[tell] > check:
			count += 1
			check = data[tell]
			tell += 1
		else:
			break
	print(math.ceil((n - count) / k))


a = int(input())
t = []
for i in range(a):
	s = [int(c) for c in input().split()]
	tup = [int(lo) for lo in input().split()]
	t.append([s[1], tup])

def main(no, arr):
	c = 0
	d = 1
	for i in arr:
		if i == d:
			c = c + 1
			d = d + 1
	e = len(arr) - c
	if e % no == 0:
		return e // no
	else:
		return e // no + 1
for z in t:
	print(main(z[0], z[1]))


import math

def count(n, k, l):
	c = 0
	for i in range(n):
		if i + 1 - c != l[i]:
			c += 1
	return math.ceil(c / k)

def main():
	tn = int(input())
	out = []
	for i in range(tn):
		nk = [int(x) for x in input().split()]
		l = [int(x) for x in input().split()]
		out.append(count(nk[0], nk[1], l))
	print(*out, sep='\n')
main()


out = []
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	p = [int(i) for i in input().split()]
	ans = 0
	i = 0
	need = 1
	cur = 0
	while i < n:
		if p[i] == need:
			i += 1
			need += 1
		else:
			cur += 1
			i += 1
			if cur == k:
				ans += 1
				cur = 0
	if cur:
		ans += 1
	out.append(ans)
for i in out:
	print(i)


def f():
	t = int(input())
	for i in range(t):
		temp = input()
		temp = temp.split(' ')
		n = int(temp[0])
		k = int(temp[1])
		temp1 = input()
		temp1 = temp1.split(' ')
		temp1 = map(int, temp1)
		temp1 = list(temp1)
		cur = 1
		total = 0
		for i in temp1:
			if i == cur:
				cur = cur + 1
			else:
				total = total + 1
		print((total + k - 1) // k)
f()


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	p = [int(x) for x in input().split()]
	i = 1
	for el in p:
		if el == i:
			i += 1
	i -= 1
	print((n - i + k - 1) // k)


import math
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	x = 1
	for el in arr:
		if el == x:
			x += 1
	print(math.ceil((n + 1 - x) / k))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	ind = l.index(1)
	p = 1
	for i in range(ind + 1, n):
		if l[i] == p + 1:
			p += 1
	print((n - p + k - 1) // k)


from math import ceil
t = int(input())
res = []
for _ in range(t):
	(n, k) = map(int, input().split())
	perm = list(map(int, input().split()))
	cnt = 0
	for i in range(n):
		if cnt + 1 == perm[i]:
			cnt += 1
	res.append(ceil((n - cnt) / k))
for i in res:
	print(i)


from math import ceil
cases = int(input())
inp = []
for _ in range(cases):
	inp.append([])
	(a, b) = input().split(' ')
	inp[-1].append((int(a), int(b)))
	inp[-1].append([int(x) for x in input().split(' ')])
for inpt in inp:
	(n, k) = inpt[0]
	st = sorted(inpt[1])
	idx = inpt[1].index(st[0])
	(p, c) = (0, 0)
	while c < n:
		if st[p] == inpt[1][c]:
			p += 1
		c += 1
	print(ceil((n - p) / k))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	lst = list(map(int, input().split()))
	i = 1
	for num in lst:
		if num == i:
			i += 1
	i -= 1
	print((n - i + k - 1) // k)


import heapq
import math
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	e = 1
	stands_right = 0
	for ai in a:
		if ai == e:
			stands_right += 1
			e += 1
	print((n - stands_right + k - 1) // k)


import math
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	r = 1
	for i in l:
		if i == r:
			r += 1
	p = n - r + 1
	print(math.ceil(p / k))


import math
t = int(input())
for _ in range(t):
	(n, k) = (int(v) for v in input().split())
	p = [int(c) for c in input().split()]
	consec = 0
	for g in p:
		if g == consec + 1:
			consec += 1
	print(math.ceil((n - consec) / k))


def main():
	t = int(input())
	for i in range(t):
		(n, k) = map(int, input().split())
		L = list(map(int, input().split()))
		cur = 1
		counter = 0
		for i in range(n):
			if L[i] == cur:
				counter += 1
				cur += 1
		n -= counter
		if n % k == 0:
			print(n // k)
		else:
			print(n // k + 1)
main()


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	m = list(map(int, input().split()))
	l = []
	(a, b) = (0, 1)
	for i in m:
		if i == b:
			a += 1
			b += 1
	s = n - a
	if s % k == 0:
		print(s // k)
	else:
		print(s // k + 1)


def fun(n, l, k):
	cnt = 0
	j = 1
	for i in range(n):
		if l[i] == j:
			cnt = cnt + 1
			j = j + 1
	if (n - cnt) % k != 0:
		print((n - cnt) // k + 1)
		return
	else:
		print((n - cnt) // k)
t = int(input())
for j in range(t):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	fun(n, l, k)


t = int(input())
for _ in range(t):
	nk = [int(x) for x in input().split()]
	n = nk[0]
	k = nk[1]
	arr = [int(x) for x in input().split()]
	step = 0
	small = arr.index(1)
	point = small
	current = 1
	while point < n - 1:
		if arr[point + 1] == current + 1:
			current += 1
			point += 1
		else:
			point += 1
	if (n - current) % k == 0:
		print((n - current) // k)
	else:
		print((n - current) // k + 1)


import math
for i in range(int(input())):
	(a, b) = map(int, input().split())
	x = list(map(int, input().split()))
	j = 1
	for k in x:
		if j == k:
			j += 1
	print(math.ceil((a - j + 1) / b))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	p = list(map(int, input().split()))
	j = 1
	r = 0
	for elem in p:
		if elem == j:
			j += 1
			r += 1
	s = n - r
	if s % k == 0:
		print(s // k)
	else:
		print(s // k + 1)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split(' '))
	lst = list(map(int, input().split(' ')))
	counter = 1
	count = 0
	for i in lst:
		if i == counter:
			counter += 1
		else:
			count += 1
	if count % k == 0:
		print(int(count / k))
	else:
		print(int(count / k) + 1)


def start():
	for _ in range(int(input())):
		(n, k) = map(int, input().split())
		arr = list(map(int, input().split()))
		ans1 = 0
		ans2 = 1
		for i in arr:
			if i == ans2:
				ans1 += 1
				ans2 += 1
		if (n - ans1) % k == 0:
			print((n - ans1) // k)
		else:
			print((n - ans1) // k + 1)
start()


T = int(input())
import math
for t in range(T):
	(n, k) = map(int, input().split(' '))
	ar = list(map(int, input().split(' ')))
	count = 0
	for ele in ar:
		if ele == count + 1:
			count += 1
	print(math.ceil((n - count) / k))


for t in range(int(input())):
	arr1 = list(map(int, input().strip().split()))[:2]
	n = arr1[0]
	k = arr1[1]
	arr = list(map(int, input().strip().split()))[:n]
	onposition = 0
	value = 1
	for x in arr:
		if x == value:
			value = value + 1
			onposition = onposition + 1
	needsort = n - onposition
	if needsort % k:
		print(needsort // k + 1)
	else:
		print(needsort // k)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	p = 0
	q = 1
	for i in range(n):
		if a[i] == q:
			p += 1
			q += 1
	temp = n - p
	if temp % k == 0:
		print(temp // k)
	else:
		print(temp // k + 1)


for _ in range(int(input())):
	(aa, bb) = map(int, input().split())
	l = list(map(int, input().split()))
	kap = 0
	kp = 1
	for i in l:
		if i == kp:
			kap += 1
			kp += 1
	anss = aa - kap
	if anss % bb == 0:
		print(anss // bb)
	else:
		print(anss // bb + 1)


for i in range(int(input())):
	(a, b) = map(int, input().split())
	ar = list(map(int, input().split()))
	c = 0
	d = 1
	for j in ar:
		if j == d:
			c = c + 1
			d = d + 1
	e = a - c
	if e % b == 0:
		print(e // b)
	else:
		print(e // b + 1)


import math as m
t = int(input())
for _ in range(t):
	(n, k) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	curr = 1
	for i in range(n):
		if arr[i] == curr:
			curr += 1
	print(m.ceil((n - curr + 1) / k))


def nag(num_arr, k, n):
	temp1 = 0
	temp2 = 1
	for x in num_arr:
		if x == temp2:
			temp1 += 1
			temp2 += 1
	temp3 = n - temp1
	if temp3 % k == 0:
		return temp3 // k
	return temp3 // k + 1
t = int(input())
while t:
	(n, k) = map(int, input().split())
	num_arr = list(map(int, input().split()))
	result = nag(num_arr, k, n)
	print(result)
	t -= 1


import math

def main():
	for t in range(int(input())):
		(a, b) = map(int, input().split())
		l = [int(x) for x in input().split()]
		j = 0
		k = 1
		while j < a:
			if l[j] == k:
				p = k
				k += 1
			j += 1
		print(int(math.ceil((a - p) / b)))
main()


for _ in range(int(input())):
	(a, b) = [int(i) for i in input().split()]
	arr = list(map(int, input().split()))
	c = 0
	f = 1
	for i in range(len(arr)):
		if arr[i] == f:
			c += 1
			f += 1
	n = a - c
	print(n // b if n % b == 0 else n // b + 1)


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	x = list(map(int, input().split()))
	of = 0
	h = 1
	for i in x:
		if i == h:
			of += 1
			h += 1
	s = a - of
	if s % b == 0:
		print(int(s / b))
	else:
		print(int(s / b) + 1)


p = int(input())
for _ in range(p):
	[n, k] = input().split(' ')
	lst = input().split(' ')
	r = 0
	tr = 1
	for i in lst:
		if int(i) == tr:
			r += 1
			tr += 1
	s = int(n) - r
	k = int(k)
	if s % k == 0:
		print(int(s / k))
	else:
		print(int(s / k + 1))


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


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = [int(x) for x in input().split()]
	(left, right) = (1, 0)
	for i in arr:
		if i == left:
			right += 1
			left += 1
	res = n - right
	if not res % k:
		print(res // k)
	else:
		print(res // k + 1)


import math
t = int(input())
for i in range(t):
	s = input().split(' ')
	(n, k) = (int(s[0]), int(s[1]))
	arr = list(map(int, input().split(' ')))
	count = 1
	for i in arr:
		if i == count:
			count += 1
	print(math.ceil((n - count + 1) / k))


import math
t = int(input(''))
A = []
B = []
C = []
for i in range(t):
	(n, k) = [int(p) for p in input('').split()]
	b = [int(p) for p in input('').split()]
	A.append(k)
	B.append(b)
	C.append(b)
for i in range(t):
	k = A[i]
	arr = B[i]
	zzz = C[i]
	momen = arr[arr.index(1):]
	track = 1
	for j in range(len(momen)):
		if momen[j] == track:
			track += 1
	track -= 1
	output = math.ceil((len(arr) - track) / k)
	print(output)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	ind = 1
	for i in range(n):
		if l[i] == ind:
			ind += 1
	uthabo = n - (ind - 1)
	if uthabo % k == 0:
		print(uthabo // k)
	else:
		print(uthabo // k + 1)


import math

def solve():
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	cnt = 0
	num = 1
	for i in arr:
		if i == num:
			cnt += 1
			num += 1
	return math.ceil((n - cnt) / k)
t = int(input())
while t:
	print(solve())
	t -= 1


def solve():
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	cv = 1
	for i in range(0, n):
		if a[i] == cv:
			cv += 1
	return (n - cv + k) // k
for t in range(0, int(input())):
	print(solve())


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	n = 1
	for i in list(map(int, input().split())):
		if i == n:
			n += 1
	print((a - n + b) // b)


for i in range(int(input())):
	nk = input()
	n = int(nk.split()[0])
	k = int(nk.split()[1])
	inp = list(map(int, input().split()))
	m = 0
	for i in range(n):
		if inp[i] == m + 1:
			m += 1
	if (n - m) % k == 0:
		print((n - m) // k)
	else:
		print((n - m) // k + 1)


def solution():
	(n, k) = (int(num) for num in input().split())
	nums = [int(num) for num in input().split()]
	j = 1
	cnt = 0
	for num in nums:
		if num == j:
			cnt += 1
			j += 1
	print((n - cnt + k - 1) // k)

def main():
	t = int(input())
	while t:
		solution()
		t -= 1
main()


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split(' ')))
	count = 1
	for num in arr:
		if count == num:
			count += 1
	res = n - (count - 1)
	if res % k == 0:
		print(res // k)
	else:
		print(res // k + 1)


t = int(input())

def sorted_subseries(a):
	s = 1
	i = 0
	while i < len(a):
		if a[i] == s:
			s += 1
		i += 1
	return s - 1
for i in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	print((len(a) - sorted_subseries(a) + k - 1) // k)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	o = 1
	for i in range(n):
		if a[i] == o:
			o += 1
	print((n - o + k) // k)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().strip().split())
	lst = list(map(int, input().strip().split()))
	to_find = 1
	num_match = 0
	for v in lst:
		if v == to_find:
			num_match += 1
			to_find += 1
	num_remain = n - num_match
	print(num_remain // k + int(num_remain % k != 0))


T = int(input())
for t in range(0, T):
	line = input().split()
	N = int(line[0])
	K = int(line[1])
	arr = map(int, input().split())
	curr = 0
	for x in arr:
		if x == curr + 1:
			curr += 1
	res = (N - curr + K - 1) // K
	print(res)


import math
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	p = list(map(int, input().split()))
	cnt = 1
	for x in p:
		if x == cnt:
			cnt += 1
	print(math.ceil((n - cnt + 1) / k))


T = int(input())
for _ in range(T):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	expect = 1
	move = 0
	for x in a:
		if x == expect:
			expect += 1
		else:
			move += 1
	print((move + k - 1) // k)


from math import ceil
for _ in ' ' * int(input()):
	(m, k) = map(int, input().split())
	b = 1
	i = 0
	for a in map(int, input().split()):
		if a == b:
			i += 1
			b += 1
	print(ceil((m - i) / k))


def mapped_read(cast):
	return map(cast, input().split())

def read_list(cast):
	return list(mapped_read(cast))

def solve():
	(n, k) = mapped_read(int)
	a = read_list(int)
	cur = 1
	for i in a:
		if cur == i:
			cur += 1
	print((n - cur + 1 + k - 1) // k)
(n,) = mapped_read(int)
for _ in range(n):
	solve()


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	p = 1
	c = 0
	for i in range(n):
		if a[i] == p:
			c += 1
			p += 1
	ans = (n - c) // k
	if (n - c) % k != 0:
		ans += 1
	print(ans)


def solve(perm, k):
	to_modify_nr = 0
	to_meet = 0
	for elem in perm:
		if elem == to_meet:
			to_meet += 1
		else:
			to_modify_nr += 1
	return (to_modify_nr + k - 1) // k

def run():
	(n, k) = (int(x) for x in input().split())
	p = [int(x) - 1 for x in input().split()]
	ans = solve(p, k)
	print(ans)
tests_nr = int(input())
for _ in range(tests_nr):
	run()


def solve():
	(n, k) = list(map(int, input().split()))
	nums = list(map(int, input().split()))
	now = 1
	su = 0
	for i in nums:
		if i == now:
			su += 1
			now += 1
	print((n - su - 1) // k + 1)
	return
TTTT = int(input())
while TTTT:
	solve()
	TTTT -= 1


for _ in range(int(input())):
	(n, x) = map(int, input().split())
	l = list(map(int, input().split()))
	a = 0
	h = 1
	for i in l:
		if i == h:
			a += 1
			h += 1
	s = n - a
	if s % x == 0:
		print(s // x)
	else:
		print(s // x + 1)


import math

def nag(l, n, k):
	c = 1
	for x in l:
		if x == c:
			c += 1
	return (n - c + k) // k
t = int(input())
while t:
	(n, k) = map(int, input().split())
	num_arr = list(map(int, input().split()))
	result = nag(num_arr, n, k)
	print(result)
	t -= 1


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	perm = list(map(int, input().split()))
	find = 1
	sub = 0
	for i in perm:
		if i == find:
			sub += 1
			find += 1
	print(-(-(n - sub) // k))


import math
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	c = 1
	for i in range(n):
		if l[i] == c:
			c += 1
	print((n - c + k) // k)


for _ in range(int(input())):
	(g, h) = map(int, input().split())
	f = list(map(int, input().split()))
	ind = f.index(1)
	p = 1
	for i in range(ind + 1, g):
		if f[i] == p + 1:
			p += 1
	print((g - p + h - 1) // h)


for __ in range(int(input())):
	(n, k) = map(int, input().split())
	nums = list(map(int, input().split()))
	count = 1
	for i in range(len(nums)):
		if nums[i] == count:
			count += 1
	print((n - count + k) // k)


def f(m, k, l):
	a = 1
	for i in l:
		if i == a:
			a += 1
	if a != 1:
		max = a - 1
	else:
		max = a
	tos = m - max
	c = tos / k
	d = tos // k
	if c == d:
		print(d)
	else:
		print(d + 1)
for t in range(int(input())):
	inp1 = list(map(int, input().split(' ')))
	m = inp1[0]
	k = inp1[1]
	inp2 = list(map(int, input().split(' ')))
	f(m, k, inp2)


from collections import deque

def main():
	a = deque(sorted(p))
	cnt = 0
	for x in p:
		if x == a[0]:
			a.popleft()
		else:
			cnt += 1
	return cnt // k + int(cnt % k != 0)
t = int(input())
for case in range(t):
	(n, k) = map(int, input().split())
	p = list(map(int, input().split()))
	print(main())


from collections import Counter
import math
op = int(input())
for _ in range(op):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	l = 1
	co = 0
	for i in range(n):
		if l == a[i]:
			l += 1
		else:
			co += 1
	if co % k == 0:
		print(co // k)
	else:
		print(co // k + 1)


import math

def sol():
	(n, k) = [int(i) for i in input().split()]
	arr = [int(i) for i in input().split()]
	(cnt, fg) = (0, 0)
	for i in range(n):
		if arr[i] == fg + 1:
			cnt += 1
			fg += 1
	print(math.ceil((n - cnt) / k))
t = int(input())
while t > 0:
	t -= 1
	sol()


for _ in range(int(input())):
	(aaaaaaaaa, bbbbbbbbbb) = map(int, input().split())
	arr = list(map(int, input().split()))
	cccccccccccc = 0
	dddddddddddd = 1
	for i in arr:
		if i == dddddddddddd:
			cccccccccccc += 1
			dddddddddddd += 1
	eeeeeeeeeeeee = aaaaaaaaa - cccccccccccc
	if eeeeeeeeeeeee % bbbbbbbbbb == 0:
		print(eeeeeeeeeeeee // bbbbbbbbbb)
	else:
		print(eeeeeeeeeeeee // bbbbbbbbbb + 1)


tests = int(input())
for _ in range(tests):
	(n, k) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	search = 1
	for ai in a:
		if ai == search:
			search += 1
	changed = n - (search - 1)
	print((changed + k - 1) // k)


import math
t = int(input())
for i in range(t):
	(n, k) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	c = 0
	c1 = 0
	for i in range(n):
		if a[i] == c + 1:
			c1 = c1 + 1
			c = c + 1
	print(math.ceil((n - c1) / k))


for j in range(int(input())):
	(bul, col) = (1, 0)
	(n, k) = map(int, input().split())
	for i in list(map(int, input().split())):
		if i == bul:
			bul += 1
			col += 1
	print((k - 1 + n - col) // k)