You are playing a game where your character should overcome different obstacles. The current problem is to come down from a cliff. The cliff has height $h$, and there is a moving platform on each height $x$ from $1$ to $h$.

Each platform is either hidden inside the cliff or moved out. At first, there are $n$ moved out platforms on heights $p_1, p_2, \dots, p_n$. The platform on height $h$ is moved out (and the character is initially standing there).

If you character is standing on some moved out platform on height $x$, then he can pull a special lever, which switches the state of two platforms: on height $x$ and $x - 1$. In other words, the platform you are currently standing on will hide in the cliff and the platform one unit below will change it state: it will hide if it was moved out or move out if it was hidden. In the second case, you will safely land on it. Note that this is the only way to move from one platform to another.

Your character is quite fragile, so it can safely fall from the height no more than $2$. In other words falling from the platform $x$ to platform $x - 2$ is okay, but falling from $x$ to $x - 3$ (or lower) is certain death. 

Sometimes it's not possible to come down from the cliff, but you can always buy (for donate currency) several magic crystals. Each magic crystal can be used to change the state of any single platform (except platform on height $h$, which is unaffected by the crystals). After being used, the crystal disappears.

What is the minimum number of magic crystal you need to buy to safely land on the $0$ ground level?


-----Input-----

The first line contains one integer $q$ ($1 \le q \le 100$) — the number of queries. Each query contains two lines and is independent of all other queries.

The first line of each query contains two integers $h$ and $n$ ($1 \le h \le 10^9$, $1 \le n \le \min(h, 2 \cdot 10^5)$) — the height of the cliff and the number of moved out platforms.

The second line contains $n$ integers $p_1, p_2, \dots, p_n$ ($h = p_1 > p_2 > \dots > p_n \ge 1$) — the corresponding moved out platforms in the descending order of their heights.

The sum of $n$ over all queries does not exceed $2 \cdot 10^5$.


-----Output-----

For each query print one integer — the minimum number of magic crystals you have to spend to safely come down on the ground level (with height $0$).


-----Example-----
Input
4
3 2
3 1
8 6
8 7 6 5 3 2
9 6
9 8 5 4 3 1
1 1
1

Output
0
1
2
0

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Mathematics

Greedy algorithms


Solutions:
import sys
import math
input = sys.stdin.readline
q = int(input())
for i in range(q):
	(h, n) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr.append(0)
	count = 0
	cur = 0
	now = arr[cur]
	cur = 1
	while cur < n:
		try:
			if now - arr[cur] == 1:
				if now - arr[cur + 1] == 2:
					now = arr[cur + 1]
					cur += 2
				else:
					count += 1
					now = arr[cur + 1] + 1
					cur += 1
			else:
				now = arr[cur] + 1
		except:
			break
	print(count)


t = int(input())
for nt in range(t):
	(h, n) = map(int, input().split())
	string = ''
	l = list(map(int, input().split()))
	ans = 0
	curr = h
	i = 1
	while curr != 0:
		if i >= n:
			break
		if l[i] == 1:
			break
		if l[i] == curr - 1 and l[(i + 1) % n] == curr - 2:
			curr = curr - 2
			i += 2
		elif l[i] == curr - 1 and l[(i + 1) % n] != curr - 2:
			if i + 1 < n:
				ans += 1
				curr = l[i + 1] + 1
				i += 1
			else:
				ans += 1
				i += 1
				curr = curr - 2
		else:
			curr = l[i] + 1
	print(ans)


import time
q = int(input())
ans = []
start = time.time()
for i in range(q):
	(h, n) = (int(j) for j in input().split())
	p = [int(j) for j in input().split()]
	a = 0
	now = 1
	while now < n:
		if now == n - 1:
			if p[now] > 1:
				a += 1
			now += 1
		elif p[now] - 1 != p[now + 1]:
			a += 1
			now += 1
		else:
			now += 2
	ans.append(a)
for i in range(q):
	print(ans[i])
finish = time.time()


R = lambda : map(int, input().split())
(q,) = R()
for _ in [0] * q:
	(h, n) = R()
	(c, d) = (1, 0)
	for x in R():
		if h - x > 1:
			d += c
			c = 0
		c ^= 1
		h = x
	print((d, d + c)[x > 1])


def solve(platforms, n):
	h = platforms[0]
	count = 0
	i = 0
	while i < n:
		if h <= 2:
			break
		if platforms[i] == h:
			i += 1
		if i < n and i + 1 < n:
			if platforms[i] == h - 1 and platforms[i + 1] == h - 2:
				h -= 2
				i += 1
			elif platforms[i] == h - 1:
				count += 1
				h -= 1
			elif platforms[i] == h - 2:
				h -= 1
			else:
				h = platforms[i] + 1
		elif i < n:
			if platforms[i] == h - 1:
				count += 1
				h -= 1
			elif platforms[i] == h - 2:
				h -= 1
			else:
				h = platforms[i] + 1
	print(count)

def main():
	q = int(input())
	for i in range(q):
		(h, n) = map(int, input().split())
		platforms = list(map(int, input().split()))
		solve(platforms, n)
main()


from heapq import heappush, heappop
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations
import sys
import bisect
import string

def I():
	return int(input())

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

def LI():
	return [int(i) for i in input().split()]

def LI_():
	return [int(i) - 1 for i in input().split()]

def StoI():
	return [ord(i) - 97 for i in input()]

def show(*inp, end='\n'):
	if show_flg:
		print(*inp, end=end)
YN = ['Yes', 'No']
mo = 10 ** 9 + 7
inf = float('inf')
show_flg = False

def solve(n, p):
	ans = 0
	while p:
		show(p)
		c = p.pop()
		if c == 0:
			break
		if len(p) > 1 and c - p[-1] > 1:
			p.append(p[-1] + 1)
		elif len(p) > 1 and c - p[-1] == 1 and (c - p[-2] == 2):
			p.pop()
		elif len(p) > 1 and c - p[-1] == 1 and (c - p[-2] > 2):
			p.pop()
			p.append(c - 2)
			ans += 1
	return ans
q = I()
for _ in range(q):
	(h, n) = LI()
	p = [-1, 0] + LI()[::-1]
	print(solve(n, p))


def crystal(h, n, l):
	if n == h:
		return 0
	count = 0
	l.append(0)
	i = 1
	while i < n:
		if l[i] - l[i + 1] >= 2:
			count += 1
			i += 1
		else:
			i += 2
	return count
tc = int(input())
for _ in range(tc):
	(h, n) = map(int, input().split())
	l = list(map(int, input().split()))
	print(crystal(h, n, l))


def main():
	import sys
	input = sys.stdin.readline
	t = int(input())
	for _ in range(t):
		(h, N) = map(int, input().split())
		A = list(map(int, input().split()))
		ans = 0
		i = 0
		while True:
			if i == N - 1:
				break
			if A[i] - A[i + 1] > 1:
				A[i] = A[i + 1] + 1
			else:
				if i == N - 2:
					if A[i] == 2:
						break
					else:
						ans += 1
						break
				if A[i + 2] == A[i + 1] - 1:
					i += 2
				else:
					ans += 1
					i += 1
		print(ans)
main()


t = int(input())
for _ in range(t):
	(h, n) = map(int, input().split())
	arr = list(map(int, input().split()))
	cur = h
	count = 0
	i = 0
	while cur > 0:
		if cur <= 2 or i == n - 1:
			break
		elif arr[i + 1] == cur - 1:
			if i + 2 <= n - 1:
				if arr[i + 2] == cur - 2:
					cur -= 2
					i += 2
				else:
					i += 1
					cur -= 2
					count += 1
			else:
				if i == n - 1 or cur <= 2:
					break
				i += 1
				cur -= 2
				count += 1
		else:
			cur = arr[i + 1] + 1
	print(count)


q = int(input())
for j in range(q):
	(h, n) = list(map(int, input().split()))
	h_list = list(map(int, input().split()))
	if n == 1:
		ans = 0
	elif n == 2:
		if h_list[1] >= 2:
			ans = 1
		else:
			ans = 0
	else:
		ans = 0
		i = 0
		while i - ans <= n - 3:
			if h_list[i - ans + 1] != h_list[i - ans + 2] + 1:
				ans += 1
			i += 2
		if n - (i - ans) == 2:
			if h_list[n - 1] >= 2:
				ans += 1
	print(ans)


t = int(input())
while t:
	(h, n) = map(int, input().split())
	l = list(map(int, input().split()))
	i = 0
	lol = 0
	cou = 0
	while h > 0 and i < len(l):
		if i + 2 >= len(l):
			lol = 1
			break
		if l[i + 1] != h - 1:
			h = l[i + 1] + 1
		elif l[i + 2] != h - 2:
			cou += 1
			h -= 2
			l[i + 1] = h
			i += 1
		else:
			h -= 2
			i += 2
	if i + 1 < len(l):
		if l[i + 1] + 1 > 2:
			cou += 1
	print(cou)
	t -= 1


q = int(input())
for i in range(q):
	(h, n) = input().split()
	h = int(h)
	n = int(n)
	p = [int(j) for j in input().split()] + [0]
	s = 1
	a = 0
	for i in range(len(p) - 1):
		if p[i] - p[i + 1] >= 2 and s % 2 == 0:
			a += 1
			s = 2
		elif p[i] - p[i + 1] >= 2 and s % 2 == 1:
			s = 2
		else:
			s += 1
	print(a)


def main():
	q = int(input())
	allans = []
	for _ in range(q):
		(h, n) = readIntArr()
		p = readIntArr()
		p.append(0)
		prevP = h + 1
		platformCnts = 0
		ans = 0
		for currP in p:
			if currP + 1 == prevP:
				platformCnts += 1
			else:
				if platformCnts % 2 == 0:
					ans += 1
				platformCnts = 2
			prevP = currP
		allans.append(ans)
	multiLineArrayPrint(allans)
	return
import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')

def oneLineArrayPrint(arr):
	print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
	print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
	print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
	return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
	dv = defaultValFactory
	da = dimensionArr
	if len(da) == 1:
		return [dv() for _ in range(da[0])]
	else:
		return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(i, j):
	print('? {} {}'.format(i, j))
	sys.stdout.flush()
	return int(input())

def answerInteractive(ans):
	print('! {}'.format(' '.join([str(x) for x in ans])))
	sys.stdout.flush()
inf = float('inf')
MOD = 10 ** 9 + 7
for _abc in range(1):
	main()


import sys
input = sys.stdin.readline
import math
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	lis = list(map(int, input().split()))
	lis.append(0)
	lis.reverse()
	dp = [0] * (m + 1)
	dp[0] = 0
	dp[1] = 0
	for i in range(2, m + 1):
		if lis[i - 1] - lis[i - 2] + 1 <= 2:
			dp[i] = dp[i - 2]
		else:
			dp[i] = 1 + dp[i - 1]
	print(dp[-1])


import sys

def input():
	return sys.stdin.readline()[:-1]

def main():
	q = int(input())
	for _ in range(q):
		(h, n) = map(int, input().split())
		s = list(map(int, input().split())) + [0]
		now = h
		ans = 0
		i = 1
		while now > 2:
			if s[i] == now - 1:
				if s[i + 1] == now - 2:
					i += 2
				else:
					ans += 1
					i += 1
				now -= 2
			else:
				now = s[i] + 1
		print(ans)
main()


q = int(input())
for _ in range(q):
	(h, n) = [int(w) for w in input().split()]
	p = [int(w) for w in input().split()]
	p.append(0)
	r = 0
	i = 1
	while i < n:
		if p[i] == p[i + 1] + 1:
			i += 2
		else:
			i += 1
			r += 1
	print(r)


q = int(input())

def fun(n):
	if n == 1:
		return 1
	if n == 2:
		return 2
	if n == 3:
		return 3
	if n == 4:
		return 4
	return n % 2 + 2
for rwre in range(q):
	(h, n) = map(int, input().split())
	l = list(map(int, input().split()))
	tab = []
	count = 1
	for i in range(1, n):
		if l[i - 1] == l[i] + 1:
			count += 1
		else:
			tab.append(count)
			tab.append(l[i - 1] - l[i] - 1)
			count = 1
	if count > 0:
		tab.append(count)
	tab.append(l[-1])
	p = []
	for i in range(len(tab)):
		if i % 2 == 0:
			p += [1] * fun(tab[i])
		else:
			p += [0] * fun(tab[i])
	h = len(p)
	p.reverse()
	i = h - 1
	wyn = 0
	while i > 2:
		if p[i - 1] == 0:
			p[i - 1] = 1
			i -= 1
		elif p[i - 2] == 1:
			i -= 2
		else:
			wyn += 1
			i -= 2
			p[i] = 1
	print(wyn)


from sys import stdin
from math import gcd
from functools import reduce
from collections import defaultdict
input = stdin.readline
put = lambda : list(map(int, input().split()))
mod = int(1000000000.0 + 7)
(q,) = put()
for _ in range(q):
	(h, n) = put()
	l = put()
	curr = h
	cost = 0
	i = 0
	while curr > 2:
		next = l[i + 1] if i + 1 < n else 0
		nextnext = l[i + 2] if i + 2 < n else 0
		if next == curr - 1:
			if nextnext == curr - 2:
				curr = nextnext
				i += 2
			else:
				cost += 1
				curr = next
				i += 1
		else:
			curr = next + 1
	print(cost)


for _ in range(int(input())):
	(h, n) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr.append(0)
	r = 0
	i = 1
	while i < n:
		if arr[i] == arr[i + 1] + 1:
			i += 2
		else:
			i += 1
			r += 1
	print(r)


t = int(input())
for z in range(t):
	delta = [int(x) for x in input().split()]
	nlevels = delta[0]
	nplatforms = delta[1]
	platforms = [int(x) for x in input().split()]
	ans = 0
	cache = [0] * nplatforms
	for i in range(nplatforms - 1):
		if platforms[i + 1] == platforms[i] - 1:
			cache[i] = 1
	ans = 0
	i = 0
	FLAG = 0
	while i < nplatforms - 2:
		if platforms[i] <= 2:
			FLAG = 1
			break
		if platforms[i + 1] != platforms[i] - 1:
			if cache[i + 1] == 1:
				i += 2
			else:
				ans += 1
				platforms[i + 1] -= 1
				i += 1
		elif platforms[i + 2] != platforms[i + 1] - 1:
			ans += 1
			platforms[i + 1] -= 1
			i += 1
		else:
			i += 2
	if FLAG == 1 or i == nplatforms - 1 or platforms[i] <= 2:
		print(ans)
		continue
	if platforms[i + 1] == 1:
		print(ans)
		continue
	print(ans + 1)


q = int(input())
for i in range(q):
	(h, n) = map(int, input().split())
	p = list(map(int, input().split()))
	p.append(0)
	ans = 0
	a = 0
	j = 2
	while j <= n:
		if p[j - 1] - p[j] > 1:
			ans += 1
			j += 1
		else:
			j += 2
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	i = 1
	ans = 0
	while i < k:
		if i < k - 1 and l[i] == l[i + 1] + 1:
			i += 1
		elif l[i] > 1:
			ans += 1
		i += 1
	print(ans)


for _ in range(int(input())):
	(h, n) = map(int, input().split())
	arr = list(map(int, input().split()))
	(i, ans) = (1, 0)
	while i < n - 1:
		if arr[i] == arr[i + 1] + 1:
			i += 2
		else:
			i += 1
			ans += 1
	if i == n - 1 and arr[i] != 1 and (arr[i] != 0):
		ans += 1
	print(ans)


from sys import stdin
from bisect import bisect_left
q = int(stdin.readline().strip())
for _ in range(q):
	(h, n) = list(map(int, stdin.readline().split()))
	moved = set(list(map(int, stdin.readline().split())))
	original = list(moved)
	original.sort()
	pos = h
	count = 0
	while pos > 0:
		if pos - 1 in moved:
			if pos - 2 in moved:
				pos -= 2
			elif pos - 2 != 0:
				count += 1
				pos -= 2
			else:
				pos -= 2
		else:
			index = bisect_left(original, pos)
			if index == 0:
				pos = 0
			else:
				pos = original[index - 1] + 1
			moved.add(pos)
	print(count)


n = int(input())
for _ in range(n):
	(h, n) = map(int, input().split())
	P = list(map(int, input().split())) + [0, 0]
	res = 0
	flg = 0
	for i in range(n):
		if flg == 1:
			flg = 0
			continue
		if P[i] - 1 >= P[i + 1]:
			P[i] = P[i + 1] + 1
			if P[i] - P[i + 2] > 2:
				P[i + 1] = P[i + 2] + 1
				res += 1
			else:
				flg = 1
	print(res)


import os, sys
from io import BytesIO
input = BytesIO(os.read(0, os.fstat(0).st_size)).readline
t = int(input())
for с in range(t):
	(h, n) = map(int, input().split())
	a = list(map(int, input().split()))
	s = 1
	pval = h
	ans = 0
	for i in range(1, n):
		cval = a[i]
		if s == 1:
			s = 2
		elif s == 2 and pval - cval == 1:
			s = 1
		elif s == 2 and pval - cval > 1:
			ans += 1
		pval = cval
	if s == 2 and a[-1] != 1:
		ans += 1
	print(ans)


def work():
	(h, n) = (int(x) for x in input().split())
	p = [int(x) for x in input().split()]
	p.append(0)
	p.append(-1)
	num = 0
	ans = 0
	while num < n:
		if p[num + 1] == p[num] - 1:
			if p[num + 2] == p[num] - 2:
				num = num + 2
			else:
				ans = ans + 1
				num = num + 1
				p[num] = p[num] - 1
		else:
			p[num] = p[num + 1] + 1
	print(ans)
q = int(input())
for i in range(q):
	work()


q = int(input())
for i in range(q):
	(h, n) = [int(j) for j in input().split()]
	a = [int(x) for x in input().split()] + [0] * 2
	(result, y) = (0, 0)
	while y < n:
		if a[y + 1] - a[y + 2] <= 1:
			y += 2
		else:
			result += 1
			a[y + 1] += 1
			y += 1
	print(result)


q = int(input())
for k in range(q):
	(h, n) = map(int, input().split())
	plat = list(map(int, input().split()))
	crystals = 0
	i = 0
	while i < n - 1:
		if plat[i] - plat[i + 1] > 1:
			plat[i] = plat[i + 1] + 1
		if plat[i + 1] + 1 == plat[i]:
			if i + 2 >= n:
				if plat[i] >= 3:
					crystals += 1
			elif plat[i + 2] + 1 != plat[i + 1]:
				crystals += 1
				plat[i + 1] -= 1
				i -= 1
			i += 1
		i += 1
	print(crystals)


for q in range(int(input())):
	(h, n) = [int(i) for i in input().split()]
	d = [int(i) for i in input().split()]
	if n == 1:
		print(0)
		continue
	ans = 0
	blocks = []
	ind = 0
	while ind < n:
		cnt = 1
		while ind < n - 1 and d[ind + 1] == d[ind] - 1:
			cnt += 1
			ind += 1
		blocks.append(cnt)
		ind += 1
	ans = 0
	blocks[0] += 1
	for b in blocks:
		ans += b & 1
	if blocks[-1] & 1 == 1 and d[n - 1] == 1:
		ans -= 1
	print(ans)


q = int(input())
size = 2 * 100000 + 1
res = []
p = [0 for i in range(size)]
d = [0 for i in range(size)]
for k in range(0, q):
	(h, n) = [int(x) for x in input().split()]
	p = list(map(int, input().split()))
	d[0] = 0
	d[1] = 1
	for i in range(2, n):
		if p[i - 1] == p[i] + 1:
			d[i] = min(d[i - 2], d[i - 1] + 1)
		else:
			d[i] = min(d[i - 2] + 2, d[i - 1] + 1)
	if p[n - 1] == 1:
		d[n] = min(d[n - 2], d[n - 1])
	elif p[n - 1] == 2:
		d[n] = min(d[n - 2] + 2, d[n - 1])
	else:
		d[n] = min(d[n - 2] + 2, d[n - 1])
	if n == 1:
		d[n] = 0
	res.append(d[n])
for i in range(0, q):
	print(res[i])


import sys

def I():
	return sys.stdin.readline().rstrip()
q = int(I())
for _ in range(q):
	(h, n) = map(int, I().split())
	p = list(map(int, I().split()))
	(i, ans) = (0, 0)
	while i < n:
		if h == p[i]:
			pass
		elif p[i] == 1:
			h = 0
		elif i < n - 1 and p[i] - 1 == p[i + 1]:
			h = p[i + 1]
		else:
			ans += 1
			h = p[i] - 1
		i += 1
	print(ans)


import bisect
import sys
input = sys.stdin.readline
q = int(input())
for _ in range(q):
	(h, n) = map(int, input().split())
	p = list(map(int, input().split())) + [0]
	cnt = 1
	ans = 0
	pos = h
	i = 1
	while True:
		if i >= n + 1:
			break
		if pos == p[i] + 1:
			pos = p[i]
			cnt += 1
			i += 1
		else:
			pos = p[i] + 1
			if cnt % 2 == 0:
				ans += 1
				cnt = 1
	print(ans)


import sys
import math
from collections import *
from functools import reduce
input = sys.stdin.readline
sys.setrecursionlimit(100000)

def li():
	return [int(i) for i in input().rstrip('\n').split(' ')]

def val():
	return int(input().rstrip('\n'))

def st():
	return input().rstrip('\n')

def sttoli():
	return [int(i) for i in input().rstrip('\n')]
for _ in range(val()):
	(n, q) = li()
	on = li()
	oncurr = set(on)
	i = tot = 0
	while i < q:
		if on[i] <= 2 or i == q - 1:
			break
		elif on[i] - 1 not in oncurr:
			i += 1
			while i < q:
				if on[i] <= 1:
					break
				if on[i] - 1 not in oncurr:
					tot += 1
				else:
					break
				i += 1
		elif on[i] - 2 in oncurr:
			i += 1
		else:
			tot += 1
			i += 2
			while i < q:
				if on[i] <= 1:
					break
				if on[i] - 1 not in oncurr:
					tot += 1
				else:
					break
				i += 1
		i += 1
	print(tot)


from sys import stdin
q = int(stdin.buffer.readline())
for _ in range(q):
	(h, n) = map(int, stdin.buffer.readline().split())
	a = list(map(int, stdin.buffer.readline().split()))
	a.append(0)
	ans = 0
	i = 1
	while i < n:
		if a[i] == a[i + 1] + 1:
			i = i + 2
		else:
			ans += 1
			i = i + 1
	print(ans)


for i in range(int(input())):
	(h, n) = map(int, input().split())
	p = list(map(int, input().split()))
	i = 1
	res = 0
	while i < n:
		if h - p[i] == 1:
			if i + 1 < n:
				if p[i] - p[i + 1] != 1:
					res += 1
					h = p[i] - 1
					i += 1
				else:
					h = p[i + 1]
					i += 2
			elif h > 2:
				res += 1
				break
			else:
				break
		else:
			h = p[i] + 1
	print(res)


import sys

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

def solve(H, N, P):
	if N == 1:
		return 0
	ans = 0
	i = 0
	h = P[1] + 1
	while i < N - 2:
		h = P[i + 1] + 1
		diff = h - P[i + 2]
		if diff > 2:
			ans += 1
			next_h = P[i + 2] + 1
			i += 1
		else:
			next_h = P[i + 2]
			i += 2
		h = next_h
	if h > P[-1] and P[-1] + 1 >= 3:
		ans += 1
	return ans
T = int(input())
for _ in range(T):
	(H, N) = map(int, input().split())
	P = get_ints()
	print(solve(H, N, P))


for _ in range(int(input())):
	(h, n) = map(int, input().split())
	P = list(map(int, input().split()))[::-1]
	P.pop()
	ans = 0
	while h > 2 and P:
		w = P.pop()
		if h - w == 1:
			if P:
				q = P.pop()
				if h - q != 2:
					ans += 1
					P.append(q)
			else:
				ans += 1
			h -= 2
		else:
			h = w + 1
			P.append(w)
	print(ans)


q = int(input())
for _ in range(q):
	(h, n) = list(map(int, input().split()))
	arr = list(map(int, input().split())) + [0]
	ans = 0
	cur = h
	for i in range(1, n):
		if arr[i] == cur:
			continue
		elif arr[i + 1] == arr[i] - 1:
			cur = arr[i] - 1
		else:
			ans += 1
	print(ans)


q = int(input())

def solve():
	(h, n) = [int(x) for x in input().split()]
	p = [int(x) for x in input().split()]
	crystal = 0
	p.append(0)
	i = 1
	while i < n:
		if p[i] - 1 > p[i + 1]:
			crystal += 1
			i += 1
		else:
			i += 2
	print(crystal)
for _ in range(q):
	solve()


from sys import stdin, stdout
import heapq
import cProfile, math
from collections import Counter, defaultdict, deque
from bisect import bisect_left, bisect, bisect_right
import itertools
from copy import deepcopy
from fractions import Fraction
import sys, threading
import operator as op
from functools import reduce
import sys
sys.setrecursionlimit(10 ** 6)
threading.stack_size(2 ** 27)
fac_warm_up = False
printHeap = str()
memory_constrained = False
P = 10 ** 9 + 7

class MergeFind:

	def __init__(self, n):
		self.parent = list(range(n))
		self.size = [1] * n
		self.num_sets = n
		self.lista = [[_] for _ in range(n)]

	def find(self, a):
		to_update = []
		while a != self.parent[a]:
			to_update.append(a)
			a = self.parent[a]
		for b in to_update:
			self.parent[b] = a
		return self.parent[a]

	def merge(self, a, b):
		a = self.find(a)
		b = self.find(b)
		if a == b:
			return
		if self.size[a] < self.size[b]:
			(a, b) = (b, a)
		self.num_sets -= 1
		self.parent[b] = a
		self.size[a] += self.size[b]
		self.lista[a] += self.lista[b]

	def set_size(self, a):
		return self.size[self.find(a)]

	def __len__(self):
		return self.num_sets

def display(string_to_print):
	stdout.write(str(string_to_print) + '\n')

def prime_factors(n):
	factors = dict()
	for i in range(2, math.ceil(math.sqrt(n)) + 1):
		while n % i == 0:
			if i in factors:
				factors[i] += 1
			else:
				factors[i] = 1
			n = n // i
	if n > 2:
		factors[n] = 1
	return factors

def all_factors(n):
	return set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))

def fibonacci_modP(n, MOD):
	if n < 2:
		return 1
	return (cached_fn(fibonacci_modP, (n + 1) // 2, MOD) * cached_fn(fibonacci_modP, n // 2, MOD) + cached_fn(fibonacci_modP, (n - 1) // 2, MOD) * cached_fn(fibonacci_modP, (n - 2) // 2, MOD)) % MOD

def factorial_modP_Wilson(n, p):
	if p <= n:
		return 0
	res = p - 1
	for i in range(n + 1, p):
		res = res * cached_fn(InverseEuler, i, p) % p
	return res

def binary(n, digits=20):
	b = bin(n)[2:]
	b = '0' * (digits - len(b)) + b
	return b

def is_prime(n):
	if n < 4:
		return True
	if n % 2 == 0:
		return False
	if n % 3 == 0:
		return False
	i = 5
	w = 2
	while i * i <= n:
		if n % i == 0:
			return False
		i += w
		w = 6 - w
	return True

def generate_primes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p]:
			for i in range(p * 2, n + 1, p):
				prime[i] = False
		p += 1
	return prime
factorial_modP = []

def warm_up_fac(MOD):
	global factorial_modP, fac_warm_up
	if fac_warm_up:
		return
	factorial_modP = [1 for _ in range(fac_warm_up_size + 1)]
	for i in range(2, fac_warm_up_size):
		factorial_modP[i] = factorial_modP[i - 1] * i % MOD
	fac_warm_up = True

def InverseEuler(n, MOD):
	return pow(n, MOD - 2, MOD)

def nCr(n, r, MOD):
	global fac_warm_up, factorial_modP
	if not fac_warm_up:
		warm_up_fac(MOD)
		fac_warm_up = True
	return factorial_modP[n] * (pow(factorial_modP[r], MOD - 2, MOD) * pow(factorial_modP[n - r], MOD - 2, MOD) % MOD) % MOD

def get_int():
	return int(stdin.readline().strip())

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

def get_list():
	return list(map(int, stdin.readline().split()))
memory = dict()

def clear_cache():
	global memory
	memory = dict()

def cached_fn(fn, *args):
	global memory
	if args in memory:
		return memory[args]
	else:
		result = fn(*args)
		memory[args] = result
		return result

def ncr(n, r):
	return math.factorial(n) / (math.factorial(n - r) * math.factorial(r))

def binary_search(i, li):
	fn = lambda x: li[x] - x // i
	x = -1
	b = len(li)
	while b >= 1:
		while b + x < len(li) and fn(b + x) > 0:
			x += b
		b = b // 2
	return x
TestCases = True
optimise_for_recursion = True

def main():
	(h, n) = get_tuple()
	li = get_list() + [0]
	res = 0
	i = 0
	while i + 1 < n and li[i] > 2:
		if li[i + 2] == li[i + 1] - 1:
			i += 2
		else:
			res += 1
			i += 1
	print(res)
if TestCases:
	for i in range(get_int()):
		main()
else:
	main() if not optimise_for_recursion else threading.Thread(target=main).start()


from collections import defaultdict, deque
for _ in range(int(input())):
	(h, n) = map(int, input().split())
	List = [int(x) for x in input().split()]
	List.append(0)
	magic = 0
	List.append(0)
	i = 1
	while i < n:
		if List[i] - 1 > List[i + 1]:
			magic += 1
			i += 1
		else:
			i += 2
	print(magic)


for _ in range(int(input())):
	(h, p) = map(int, input().split())
	o = list(map(int, input().split()))
	o.append(0)
	crystals = 0
	height = 1
	while height < p:
		if o[height] - 1 > o[height + 1]:
			crystals += 1
			height += 1
		else:
			height += 2
	print(crystals)


import sys
from collections import deque
input = sys.stdin.readline

def getcnt(fromplatform, toplatform):
	return (fromplatform - toplatform) // 2
for _ in range(int(input())):
	(h, n) = list(map(int, input()[:-1].split()))
	platforms = deque(map(int, input()[:-1].split()))
	currenth = h
	platforms.popleft()
	platforms.append(-200)
	ans = 0
	while currenth > 2:
		if currenth - 1 == platforms[0]:
			if currenth - 2 == platforms[1]:
				platforms.popleft()
				platforms.popleft()
				currenth -= 2
			else:
				platforms.popleft()
				ans += 1
				currenth = platforms[0] + 1
		else:
			currenth = platforms[0] + 1
	print(ans)


def scale(p):
	offset = 0
	last = 0
	newp = []
	for pi in p:
		diff = pi - last
		if diff > 2:
			offset += diff - 2
		newp.append(pi - offset)
		last = pi
	return newp

def f(h, p):
	x = 0
	y = 0
	for i in range(3, h + 1):
		a = 1 if i - 1 in p else 0
		b = 1 if i - 2 in p else 0
		z = min(y + a, x + (1 - a) + (1 - b))
		(y, x) = (z, y)
	return y
q = int(input())
for _ in range(q):
	(h, n) = map(int, input().split(' '))
	p = list(map(int, input().split(' ')))
	p.reverse()
	p = scale(p)
	h = p[-1]
	s = set(p)
	print(f(h, s))


from sys import stdin, stdout
tests = int(stdin.readline().strip())
for t in range(tests):
	(n, m) = map(int, stdin.readline().strip().split())
	s = list(map(int, stdin.readline().strip().split()))
	s = s[::-1]
	cur = n
	ans = 0
	while cur > 0 and len(s) != 0:
		if cur <= 2:
			break
		while len(s) > 0 and s[-1] >= cur:
			s.pop()
		if len(s) == 0:
			break
		if cur - s[-1] > 1:
			cur = s[-1] + 1
			continue
		if len(s) == 1:
			ans += 1
			break
		if s[-2] + 1 == s[-1]:
			cur = s[-2]
			continue
		ans += 1
		cur = s[-2] + 1
	print(ans)


import sys
input = sys.stdin.readline
q = int(input())
for testcases in range(q):
	(h, n) = map(int, input().split())
	P = list(map(int, input().split()))
	P.append(-10)
	NOW = h
	ANS = 0
	ind = 1
	while NOW >= 3:
		if P[ind] < NOW - 1:
			NOW = P[ind] + 1
			continue
		if P[ind] == NOW - 1 and P[ind + 1] == NOW - 2:
			NOW -= 2
			ind += 2
			continue
		if P[ind] == NOW - 1 and P[ind + 1] != NOW - 2:
			NOW -= 2
			ind += 1
			ANS += 1
	print(ANS)


for T in range(int(input())):
	(h, n) = map(int, input().split())
	(*a,) = map(int, input().split())
	a.append(0)
	(ans, cur) = (0, h)
	for i in range(n):
		if cur == a[i]:
			continue
		if a[i] - 1 != a[i + 1]:
			ans += 1
		cur = a[i] - 1
	print(ans)


Q = int(input())
for q in range(Q):
	(h, n) = tuple(map(int, input().split()))
	arr = list(map(int, input().split()))
	arr.append(0)
	i = 0
	ans = 0
	now = arr[0]
	while i < len(arr) - 2:
		x = arr[i + 1]
		if now != x + 1:
			now = x + 1
		elif now == arr[i + 2] + 2:
			now = arr[i + 2]
			i += 2
		else:
			now = arr[i + 2] + 1
			i += 1
			ans += 1
	print(ans)


q = int(input())
for j in range(q):
	d = {}
	(h, n) = map(int, input().split())
	P = list(map(int, input().split()))
	P.append(0)
	k = 0
	j = 0
	while 1:
		try:
			if P[j + 1] - P[j + 2] == 1:
				h = P[j + 2]
				j = j + 2
			else:
				h = P[j + 2]
				j = j + 1
				k += 1
		except:
			break
	print(k)


q = int(input())
for _ in range(q):
	(h, n) = map(int, input().split())
	P = [int(i) for i in input().split()]
	P += [0]
	n += 1
	cur = h
	next = 1
	ans = 0
	while cur > 0 and next <= n - 2:
		if P[next + 1] < P[next] - 1:
			cur = P[next] - 1
			next += 1
			ans += 1
		else:
			cur = P[next + 1]
			next += 2
	print(ans)


for _ in range(int(input())):
	(h, n) = map(int, input().split())
	a = [int(x) for x in input().split()]
	gg = a[0]
	flag = 0
	ans = 0
	for i in range(1, n):
		if gg - 1 == a[i] and flag == 0:
			flag = 1
		elif gg - 1 == a[i] and flag == 1:
			flag = 0
		elif flag == 0:
			flag = 1
		else:
			ans += 1
		gg = a[i]
	if a[n - 1] >= 2:
		if flag == 1:
			ans += 1
	print(ans)


import sys
q = int(input())
for _ in range(q):
	(h, n) = map(int, sys.stdin.readline().split())
	p = iter(list(map(int, sys.stdin.readline().split())) + [0])
	cost = 0
	akt = next(p)
	a = next(p)
	if a == 0:
		print(0)
	else:
		b = next(p)
		while True:
			if a - b == 1:
				akt = b
				if akt == 0:
					break
				else:
					a = next(p)
				if a == 0:
					break
				else:
					b = next(p)
			else:
				cost += 1
				akt = a - 1
				a = b
				if a == 0:
					break
				else:
					b = next(p)
		print(cost)


t = int(input())
for _ in range(t):
	(n, p) = list(map(lambda x: int(x), input().split()))
	platforms = list(map(lambda x: int(x), input().split()))
	platforms.append(0)
	crystals = 0
	i = 1
	current = platforms[0]
	while i < p:
		if platforms[i] == current - 1:
			if platforms[i + 1] == current - 2:
				current = platforms[i + 1]
				i = i + 2
				continue
			else:
				crystals += 1
				current = platforms[i + 1] + 1
				i += 1
				continue
		else:
			current = platforms[i] + 1
	print(crystals)


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
from heapq import heappush, heappop, heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10 ** 9 + 7
inf = float('inf')

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

def LI():
	return list(map(int, sys.stdin.readline().split()))
q = I()
for _ in range(q):
	(h, n) = LI()
	p = LI() + [0]
	ans = 0
	i = 1
	while i < n:
		if p[i] == p[i + 1] + 1:
			i += 2
		else:
			i += 1
			ans += 1
	print(ans)


import sys
import math
from collections import defaultdict
from itertools import combinations
from itertools import permutations
input = lambda : sys.stdin.readline().rstrip()
read = lambda : map(int, input().split())

def write(*args, sep='\n'):
	for i in args:
		sys.stdout.write('{}'.format(i) + sep)
INF = float('inf')
MOD = int(1000000000.0 + 7)
for q in range(int(input())):
	(h, n) = read()
	arr = list(read()) + [0]
	if n == 1:
		write(0)
		continue
	ans = 0
	cur = h
	for i in range(1, n):
		if cur == arr[i]:
			continue
		elif arr[i + 1] == arr[i] - 1:
			cur = arr[i] - 1
		else:
			ans += 1
	write(ans)


import sys

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

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def list4d(a, b, c, d, e):
	return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]

def ceil(x, y=1):
	return int(-(-x // y))

def INT():
	return int(input())

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

def LIST(N=None):
	return list(MAP()) if N is None else [INT() for i in range(N)]

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7
for _ in range(INT()):
	(H, N) = MAP()
	A = LIST() + [0] * 2
	ans = 0
	i = 0
	while i < N:
		if A[i + 1] - A[i + 2] <= 1:
			i += 2
		else:
			ans += 1
			A[i + 1] += 1
			i += 1
	print(ans)


Q = int(input())
for q in range(Q):
	(H, N) = map(int, input().split())
	A = list(map(int, input().split()))
	i = 0
	ans = 0
	while i < N - 1:
		if A[i] == A[i + 1] + 1:
			if i >= N - 2:
				if A[i] > 2:
					ans += 1
				break
			elif A[i] != A[i + 2] + 2:
				ans += 1
				A[i + 1] = A[i + 2] + 1
				i += 1
			else:
				i += 2
		else:
			A[i] = A[i + 1] + 1
	print(ans)


import sys, os
from io import BytesIO, IOBase
from math import floor, gcd, fabs, factorial, fmod, sqrt, inf, log
from collections import defaultdict as dd, deque
from heapq import merge, heapify, heappop, heappush, nsmallest
from bisect import bisect_left as bl, bisect_right as br, bisect
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(stdin, stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
mod = pow(10, 9) + 7
mod2 = 998244353

def inp():
	return stdin.readline().strip()

def iinp():
	return int(inp())

def out(var, end='\n'):
	stdout.write(str(var) + '\n')

def outa(*var, end='\n'):
	stdout.write(' '.join(map(str, var)) + end)

def lmp():
	return list(mp())

def mp():
	return map(int, inp().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(m, val) for j in range(n)]

def ceil(a, b):
	return (a + b - 1) // b
S1 = 'abcdefghijklmnopqrstuvwxyz'
S2 = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'

def isprime(x):
	if x <= 1:
		return False
	if x in (2, 3):
		return True
	if x % 2 == 0:
		return False
	for i in range(3, int(sqrt(x)) + 1, 2):
		if x % i == 0:
			return False
	return True
for _ in range(iinp()):
	(h, n) = mp()
	arr = lmp()
	i = 0
	ans = 0
	arr.append(0)
	while i < n - 1:
		if arr[i + 2] == arr[i + 1] - 1:
			i += 1
		else:
			ans += 1
		i += 1
	print(ans)


t = int(input())
import sys
input = sys.stdin.readline
while t > 0:
	t -= 1
	(h, n) = map(int, input().split())
	a = [int(x) for x in input().split()]
	a.append(0)
	c = 0
	i = 0
	while i < n - 1:
		if a[i] - a[i + 1] >= 2:
			a[i] = a[i + 1] + 1
		elif a[i + 2] == a[i] - 2:
			i += 2
		else:
			c += 1
			a[i + 1] -= 1
			i += 1
	print(c)


tests = int(input())
for i in range(tests):
	(h, n) = [int(x) for x in input().split()]
	line = [int(x) for x in input().split()]
	total_cost = 0
	k = 0
	length = 0
	while k < len(line) and line[k] != 1:
		length += 1
		if k < len(line) - 1 and line[k] == line[k + 1] + 1:
			pass
		else:
			if length % 2 == 0:
				total_cost += 1
			k += 1
			break
		k += 1
	length = 1
	while k < len(line) and line[k] != 1:
		if k < len(line) - 1 and line[k] == line[k + 1] + 1:
			length += 1
		else:
			if length % 2 == 0:
				pass
			else:
				total_cost += 1
			length = 1
		k += 1
	print(total_cost)


import os
import sys
from io import BytesIO, IOBase

def main():
	for _ in range(int(input())):
		(h, n) = map(int, input().split())
		p = list(map(int, input().split()))
		ans = 0
		i = 1
		while i < n:
			if i < n - 1:
				if p[i] - p[i + 1] == 1:
					i += 1
				else:
					ans += 1
			elif p[i] != 1:
				ans += 1
			i += 1
		print(ans)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


for _ in range(int(input())):
	(h, n) = map(int, input().split())
	p = [int(i) for i in input().split()] + [0]
	only_ones = []
	local_ones = [1]
	for (ind, p_i) in enumerate(p[1:]):
		if p[ind] - p_i == 1:
			local_ones.append(1)
		else:
			only_ones.append(local_ones.copy())
			local_ones = [1]
	else:
		only_ones.append(local_ones)
	if len(only_ones) == 1:
		print(0)
	else:
		number_of_magic_crystals = 1 if len(only_ones[0]) % 2 == 0 else 0
		for ones in only_ones[1:len(only_ones) - 1]:
			if len(ones) % 2 == 1:
				number_of_magic_crystals += 1
		print(number_of_magic_crystals)


import sys
import bisect
import heapq
Ri = lambda : [int(x) for x in sys.stdin.readline().split()]
ri = lambda : sys.stdin.readline().strip()

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

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def list4d(a, b, c, d, e):
	return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]

def ceil(x, y=1):
	return int(-(-x // y))

def INT():
	return int(input())

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

def LIST(N=None):
	return list(MAP()) if N is None else [INT() for i in range(N)]

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
INF = 10 ** 18
MOD = 10 ** 9 + 7
for _ in range(int(ri())):
	(h, n) = Ri()
	a = Ri()
	ans = 0
	pos = h
	ite = 1
	while pos != 0 and ite <= n - 1:
		if pos == 1 or pos == 2 or pos == 0:
			break
		if ite + 1 <= n - 1 and a[ite + 1] == pos - 2:
			pos = pos - 2
			ite = ite + 2
			continue
		if ite <= n - 1 and a[ite] == pos - 1:
			ans += 1
			pos = pos - 1
			ite = ite + 1
			continue
		pos = a[ite] + 1
	print(ans)


from sys import stdin, stdout
input = stdin.readline

def case():
	(h, n) = map(int, input().split())
	platforms = [int(i) for i in input().split()] + [0]
	i = 0
	pos = platforms[i]
	crystal_counter = 0
	while platforms[i] and i + 1 < n:
		if platforms[i] - platforms[i + 1] > 1:
			platforms[i] = platforms[i + 1] + 1
			continue
		if platforms[i] - platforms[i + 2] > 2:
			crystal_counter += 1
			platforms[i + 1] = platforms[i + 2] + 1
			i += 1
		elif platforms[i] - platforms[i + 2] == 2:
			i += 2
	return crystal_counter

def main():
	ans = []
	q = int(input())
	for _ in range(q):
		ans.append(str(case()))
	stdout.write('\n'.join(ans))
main()


for h in range(int(input())):
	(h, n) = map(int, input().strip().split())
	arr = list(map(int, input().strip().split()))
	arr.append(0)
	ans = 0
	curr = h
	for i in range(n):
		if curr == arr[i]:
			continue
		if arr[i] - 1 != arr[i + 1]:
			ans += 1
		curr = arr[i] - 1
	print(ans)


for _ in range(int(input())):
	(h, n) = map(int, input().split())
	arr = list(map(int, input().split()))
	dp = [0] * (n + 1)
	dp[0] = 0
	for i in range(1, n):
		if arr[i - 1] - arr[i] > 0:
			dp[i] = 1 + dp[i - 1]
		if i - 2 >= 0 and arr[i - 2] - arr[i] >= 2 and (arr[i - 1] - arr[i] == 1):
			dp[i] = min(dp[i], dp[i - 2])
	if arr[n - 1]:
		res = dp[n - 1]
	if n - 2 >= 0 and arr[n - 2] >= 2 and (arr[n - 1] == 1):
		res = min(res, dp[n - 2])
	print(res)


q = int(input())
while q:
	q -= 1
	(h, n) = [int(x) for x in input().split()]
	p = list(map(int, input().split()))
	for i in range(10):
		p.append(-10)
	cur = h
	ans = 0
	i = 1
	while cur > 2:
		if p[i] == cur - 1:
			if p[i + 1] != cur - 2:
				ans += 1
				cur -= 2
				i += 1
			else:
				cur -= 2
				i += 2
		else:
			cur = p[i] + 1
	print(ans)


import sys

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

def input():
	return sys.stdin.readline().rstrip('\n')

def oint():
	return int(input())
q = oint()
for _ in range(q):
	(h, n) = rint()
	p = list(rint())
	cur = h
	cnt = 0
	for i in range(1, n):
		if cur <= p[i]:
			continue
		cur = p[i] + 1
		if p[i] == cur - 1:
			if i + 1 > n - 1:
				if cur > 2:
					cnt += 1
					cur -= 2
					break
			elif p[i + 1] == cur - 2:
				cur -= 2
				continue
			else:
				cnt += 1
				cur -= 2
				continue
	print(cnt)


q = int(input())
for _ in range(q):
	(h, n) = map(int, input().split())
	p = list(map(int, input().split())) + [0]
	cnt = 0
	i = 1
	while i <= n - 1:
		if p[i] + 1 - p[i + 1] >= 3:
			cnt += 1
		elif p[i] - p[i + 1] == 1:
			i += 1
		i += 1
	print(cnt)


import sys, os, io
from sys import stdin
from math import log, gcd, ceil
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop
import math
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def primeFactors(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(int(i))
			n = n / i
	if n > 2:
		l.append(n)
	return list(set(l))

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime

def countdig(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def prefix_sum(arr):
	r = [0] * (len(arr) + 1)
	for (i, el) in enumerate(arr):
		r[i + 1] = r[i] + el
	return r

def divideCeil(n, x):
	if n % x == 0:
		return n // x
	return n // x + 1

def si():
	return input()

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

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

def ws(s):
	sys.stdout.write(s + '\n')

def wi(n):
	sys.stdout.write(str(n) + '\n')

def wia(a):
	sys.stdout.write(' '.join([str(x) for x in a]) + '\n')
t = 1
t = int(input())
for _ in range(t):
	(h, n) = li()
	p = li()
	p.sort(reverse=True)
	consecutive = []
	curr = 0
	s = []
	for i in range(1, n):
		if p[i] + 2 == p[i - 1] + 1:
			if curr == 0:
				s.append(p[i])
			curr += 1
		else:
			consecutive.append(curr + 1)
			curr = 0
	consecutive.append(curr + 1)
	res = 0
	f = 0
	for i in range(len(consecutive)):
		if consecutive[i] % 2 == 0:
			res += 1
		if i != len(consecutive) - 1:
			consecutive[i + 1] += 1
		elif consecutive[i] % 2 == 0 and p[-1] == 1:
			res -= 1
	print(res)


for itr in range(int(input())):
	(h, o) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	a = a[::-1]
	a.pop(-1)
	ans = 0
	while h > 2:
		if len(a) == 0:
			break
		if h - 1 == a[-1]:
			if len(a) > 1 and h - 2 == a[-2]:
				h -= 2
				a.pop(-1)
				a.pop(-1)
			else:
				ans += 1
				h -= 2
				a.pop(-1)
		else:
			h = a[-1] + 1
	print(ans)


q = int(input())
for _ in range(q):
	(h, n) = map(int, input().split())
	l = list(map(int, input().split()))
	l.append(0)
	no_of_crystals = 0
	i = 2
	while i <= n:
		if l[i - 1] - l[i] > 1:
			no_of_crystals += 1
			i += 1
		else:
			i += 2
	print(no_of_crystals)


import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
q = int(input())
for i in range(q):
	(h, n) = list(map(int, input().split()))
	p = list(map(int, input().split()))
	if n == 1:
		print(0)
	else:
		ans = 0
		arr = []
		for j in range(n - 1):
			arr.append(p[j] - p[j + 1])
		arr.append(p[-1])
		j = 0
		while j < n:
			if arr[j] > 1:
				arr[j] = 1
			elif j != n - 1:
				if arr[j + 1] == 1:
					j += 2
				else:
					ans += 1
					arr[j + 1] = 1
					j += 1
			else:
				j += 1
		print(ans)


n = int(input())
for z in range(n):
	(h, am) = map(int, input().split())
	arr = list(map(int, input().split()))
	ch = h
	i = 1
	ac = 0
	while i < am:
		if ch - arr[i] >= 2:
			ch = arr[i] + 1
		elif i < am - 1 and arr[i + 1] == ch - 2 or ch == 2:
			ch -= 2
			i += 2
		else:
			ch -= 2
			i += 1
			ac += 1
	print(ac)


for q in range(int(input())):
	(h, n) = map(int, input().split())
	a = [int(x) for x in input().split()]
	c = 0
	a.append(0)
	i = 1
	while i < n:
		if a[i] - 1 > a[i + 1]:
			c += 1
			i += 1
		else:
			i += 2
	print(c)


t = int(input())
for _ in range(t):
	(h, n) = map(int, input().split())
	p = list(map(int, input().split()))
	p.reverse()
	s = n - 1
	c = 0
	l = h
	while 1:
		if l < 3:
			break
		if s < 1:
			break
		if l - p[s - 1] > 1:
			l = p[s - 1] + 1
		elif s < 2:
			if p[s] - 2 > 0:
				c += 1
			break
		elif l - p[s - 2] == 2:
			l = p[s - 2]
			s -= 2
		else:
			c += 1
			l -= 2
			s -= 1
	print(c)


import sys
input = sys.stdin.readline
q = int(input())
for i in range(q):
	(h, n) = map(int, input().split())
	l = list((int(i) for i in input().split()))
	l.append(0)
	level = 1
	crystal = 0
	while level < n:
		if l[level + 1] == l[level] - 1:
			level += 2
		else:
			crystal += 1
			level += 1
	print(crystal)


import sys
import itertools
import math
import collections
from collections import Counter

def pow(x, y, mod):
	r = 1
	x = x % mod
	while y > 0:
		if y & 1:
			r = r * x % mod
		y = y >> 1
		x = x * x % mod
	return r

def sieve(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * 2, n + 1, p):
				prime[i] = False
		p += 1
	prime[0] = prime[1] = False
	r = [p for p in range(n + 1) if prime[p]]
	return r

def divs(n, start=1):
	r = []
	for i in range(start, int(math.sqrt(n) + 1)):
		if n % i == 0:
			if n / i == i:
				r.append(i)
			else:
				r.extend([i, n // i])
	return r

def cdiv(n, k):
	return n // k + (n % k != 0)

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

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

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

def lcm(a, b):
	return abs(a * b) // math.gcd(a, b)

def prr(a, sep=' '):
	print(sep.join(map(str, a)))

def dd():
	return collections.defaultdict(int)
q = ii()
for _ in range(q):
	(h, n) = mi()
	d = li()
	d.append(0)
	d.append(0)
	i = 0
	r = 0
	while i < n - 1:
		if d[i] <= 2:
			break
		if d[i] - d[i + 1] >= 2:
			d[i] = d[i + 1] + 1
			continue
		if d[i] - d[i + 2] == 2:
			i += 2
		else:
			r += 1
			d[i + 1] = d[i + 2] + 1
			i = i + 1
	print(r)


t = int(input())
while t > 0:
	t = t - 1
	hn = input().split()
	h = int(hn[0])
	n = int(hn[1])
	pos = input().split()
	pos = [int(val) for val in pos]
	curr = h
	curr_pos = 1
	no_crystal = 0
	while curr > 2:
		if curr_pos >= len(pos):
			break
		if curr - 1 == pos[curr_pos]:
			if curr_pos == len(pos) - 1 or curr - 2 != pos[curr_pos + 1]:
				no_crystal = no_crystal + 1
				curr = curr - 2
				curr_pos = curr_pos + 1
			else:
				curr_pos = curr_pos + 2
		else:
			curr = pos[curr_pos] + 1
	print(no_crystal)


import sys
readline = sys.stdin.readline
read = sys.stdin.read
ns = lambda : readline().rstrip()
ni = lambda : int(readline().rstrip())
nm = lambda : map(int, readline().split())
nl = lambda : list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

def solve():
	(h, n) = nm()
	l = nl() + [0] * 2
	idx = 0
	c = 0
	while idx < n - 1:
		if l[idx] <= l[idx + 1] + 1:
			if l[idx + 2] + 2 >= l[idx]:
				idx += 2
				continue
			else:
				c += 1
				idx += 1
				l[idx] = l[idx + 1] + 1
		else:
			l[idx] = l[idx + 1] + 1
	print(c)
	return
T = ni()
for _ in range(T):
	solve()


import os, sys
from io import BytesIO
input = BytesIO(os.read(0, os.fstat(0).st_size)).readline
import bisect
for j in range(int(input())):
	(h, n) = map(int, input().split())
	sorts = list(map(int, input().split()))
	sorts.reverse()
	moves = 0
	current = sorts[-1]
	while current > 2:
		ind = bisect.bisect_left(sorts, current)
		if sorts[ind] >= current and ind != 0:
			ind -= 1
		h1 = sorts[ind]
		if current != sorts[ind]:
			current = h1 + 1
		if current <= 2:
			break
		if ind - 1 >= 0:
			if abs(sorts[ind - 1] - h1) == 1:
				current = sorts[ind - 1]
			else:
				moves += 1
				current = sorts[ind - 1] + 1
		elif current == sorts[0] or abs(current - sorts[0]) == 2:
			break
		else:
			moves += 1
			break
	print(moves)


q = int(input())
for _ in range(q):
	(h, n) = map(int, input().split())
	ps = list(map(int, input().split())) + [0, 0]
	ps.reverse()
	cur = n - 1
	crystals = 0
	while ps and ps[-1] > 1:
		if ps[-2] == h - 1:
			if ps[-3] == h - 2:
				ps.pop()
				ps.pop()
			else:
				ps.pop()
				ps[-1] = h - 2
				crystals += 1
			h -= 2
		else:
			ps[-1] = ps[-2] + 1
			h = ps[-1]
	print(crystals)


from sys import stdin, stdout
from math import gcd, sqrt, factorial
from collections import deque, defaultdict
input = stdin.readline
R = lambda : map(int, input().split())
I = lambda : int(input())
S = lambda : input().rstrip('\n')
L = lambda : list(R())
P = lambda x: stdout.write(x)
lcm = lambda x, y: x * y // gcd(x, y)
hg = lambda x, y: (y + x - 1) // x * x
pw = lambda x: 0 if x == 1 else 1 + pw(x // 2)
chk = lambda x: chk(x // 2) if not x % 2 else True if x == 1 else False
sm = lambda x: (x ** 2 + x) // 2
N = 10 ** 9 + 7
for _ in range(I()):
	(h, n) = R()
	a = L() + [0]
	(ans, p) = (0, h)
	for i in range(n):
		if a[i] == p:
			continue
		if a[i] - 1 != a[i + 1]:
			ans += 1
		p = a[i] - 1
	print(ans)


t = int(input())
for q in range(t):
	(h, n) = list(map(int, input().split()))
	p = list(map(int, input().split()))
	s = 0
	i = 1
	while h > 2 and i < n:
		if h - p[i] == 1:
			if i + 1 < n:
				if p[i] - p[i + 1] > 1:
					s += 1
					h = p[i] - 1
					i += 1
				else:
					h = p[i + 1]
					i += 2
			elif p[i] == 1:
				h = 0
			else:
				s += 1
				h = p[i] - 1
				i += 1
		else:
			h = p[i] + 1
	print(s)


q = int(input())
for i in range(q):
	(h, n) = map(int, input().split())
	p = list(map(int, input().split()))
	used = [0]
	for i in range(1, n):
		if i == 1:
			used.append(1)
		elif p[i] >= 1:
			var = 10000000000000
			if p[i - 1] - p[i] == 1:
				used.append(used[i - 2])
			else:
				used.append(used[i - 1] + 1)
	i = n - 1
	ans = 0
	if p[i] > 2:
		print(used[-1])
	elif n >= 2 and p[i] == 1:
		print(min(used[-2], used[-1]))
	else:
		print(used[-1])


def mp():
	return map(int, input().split())
t = int(input())
for tt in range(t):
	(h, n) = mp()
	a = list(mp()) + [0]
	ans = 0
	last = h
	i = 1
	while i < n:
		last = min(last, a[i] + 1)
		if a[i + 1] == last - 2:
			last = a[i + 1]
			i += 2
		else:
			ans += 1
			last -= 2
			i += 1
	print(ans)


import sys
input = sys.stdin.readline
Q = int(input())
Query = []
for _ in range(Q):
	(H, N) = map(int, input().split())
	A = list(map(int, input().split()))
	Query.append((H, N, A))
for (H, N, A) in Query:
	A.append(0)
	now = H
	i = 0
	c = 0
	while now > 0:
		if now - A[i + 1] > 1:
			now = A[i + 1] + 1
		elif i + 2 >= N + 1:
			break
		elif now - A[i + 2] > 2:
			i += 1
			c += 1
			now -= 2
		else:
			i += 2
			now -= 2
	print(c)


for _ in range(int(input())):
	(h, n) = map(int, input().split())
	p = [int(o) for o in input().split()]
	ans = 0
	p.append(0)
	i = 0
	while p[i] > 2 and i < n:
		if p[i + 1] != p[i] - 1:
			p[i] = p[i + 1] + 1
		elif p[i + 1] == p[i] - 1 and p[i + 2] == p[i] - 2:
			i += 2
		else:
			p[i + 1] = p[i] - 2
			i += 1
			ans += 1
	print(ans)


from sys import stdin
from collections import defaultdict
input = stdin.readline
for _ in range(int(input())):
	(h, n) = map(int, input().split())
	p = sorted([0] + [*map(int, input().split())])
	c = h
	costs = defaultdict(lambda : 10 ** 10)
	costs[h] = 0
	while len(p) != 0:
		if p[-1] == c:
			p.pop()
			continue
		if c - p[-1] > 2:
			costs[p[-1] + 2] = min(costs[p[-1] + 2], costs[c], costs[c - 1])
			c = p[-1] + 2
		if c - p[-1] <= 2:
			if p[-1] == c - 1:
				if len(p) > 1 and p[-2] == c - 2:
					costs[c - 2] = min(costs[c - 2], costs[c])
					costs[c - 1] = min(costs[c - 1], costs[c] + 1)
				else:
					costs[c - 2] = min(costs[c - 2], costs[c] + 1)
					costs[c - 1] = min(costs[c - 1], costs[c] + 1)
			elif p[-1] == c - 2:
				costs[c - 1] = min(costs[c - 1], costs[c])
				costs[c - 2] = min(costs[c - 2], costs[c] + 1)
			else:
				raise ValueError
			c -= 1
	ans = min(costs[2], costs[1], costs[0])
	print(ans)


from math import *
t = int(input())
for i in range(t):
	(n, r) = map(int, input().split())
	l = list(map(int, input().split()))
	l.append(0)
	l = l[::-1]
	if n <= 2:
		print(0)
	else:
		ct = 0
		i = r
		while i > 1:
			if l[i] - l[i - 1] == 1 and l[i] - l[i - 2] != 2:
				ct += 1
				l[i - 1] -= 1
				i -= 1
			elif l[i] - l[i - 1] == 1:
				i -= 2
			else:
				l[i] = l[i - 1] + 1
		print(ct)


q = int(input(''))
for _ in range(q):
	a = input('').split(' ')
	h = int(a[0])
	n = int(a[1])
	p = list(map(int, input('').split(' ')))
	p.append(-2)
	d = {0: True}
	ans = 0
	for a in p:
		d[a] = True
	cur = h
	i = 1
	while i < n:
		if cur <= 2:
			break
		if p[i] != cur - 1:
			cur = p[i] + 1
		elif cur - 2 != p[i + 1]:
			i = i + 1
			ans = ans + 1
			cur = cur - 2
		else:
			i = i + 2
			cur = cur - 2
	print(ans)


for i in range(int(input())):
	(h, n) = map(int, input().split())
	p = list(map(int, input().split()))
	p.append(0)
	s = set(p)
	ans = 0
	i = 1
	while i < n + 1 and h > 2:
		if h - 1 in s:
			h -= 2
			while i < n + 1 and p[i] >= h:
				i += 1
			if h not in s:
				ans += 1
		else:
			h = p[i] + 1
	print(ans)


from sys import stdin
a = lambda : stdin.readline().split()
for _ in range(int(stdin.readline())):
	(h, n) = map(int, a())
	lst = [*map(int, a())]
	if n == 1:
		print(0)
		continue
	(cout, item, res) = (1, 1, 0)
	for (i, x) in enumerate(lst[1:]):
		if x + 1 == lst[i]:
			cout += 1
		else:
			if item == 1:
				if cout % 2 == 0:
					res += 1
				item = 2
			elif cout % 2 == 1:
				res += 1
			cout = 1
	if lst[-1] != 1:
		if item == 1:
			if cout % 2 == 0:
				res += 1
		elif cout % 2 == 1:
			res += 1
	print(res)


T = int(input())
for t in range(T):
	(h, n) = list(map(int, input().strip().split(' ')))
	steps = list(map(int, input().strip().split(' ')))
	steps.append(0)
	cur = n
	danger = 0
	ret = 0
	index = 1
	cur = steps[index] + 1
	while cur > 2:
		if steps[index + 1] == cur - 2:
			index += 2
		else:
			index += 1
			ret += 1
		cur = steps[index] + 1
	print(ret)


q = int(input())
for i in range(q):
	(h, n) = map(int, input().split())
	pi = list(map(int, input().split()))
	pi.append(0)
	num = 10 ** 9 + 1
	dp = [[num, num] for i in range(n + 1)]
	dp[0][0] = 0
	for i in range(n):
		dp[i + 1][1] = min(dp[i + 1][1], dp[i][0])
		dp[i + 1][1] = min(dp[i + 1][1], dp[i][1] + 1)
		if i < n and pi[i + 1] == pi[i] - 1:
			dp[i + 1][0] = min(dp[i + 1][0], dp[i][1])
		if i < n and pi[i + 1] == pi[i] - 2:
			dp[i + 1][0] = min(dp[i + 1][0], dp[i][0] + 1)
		if i < n - 1 and pi[i + 1] == pi[i] - 1 and (pi[i + 2] == pi[i] - 2):
			dp[i + 2][0] = min(dp[i + 2][0], dp[i][0])
		if pi[i] == 1:
			dp[i + 1][0] = min(dp[i + 1][0], dp[i][0])
			dp[i + 1][0] = min(dp[i + 1][0], dp[i][1])
	print(min(dp[-1]))


from math import *
from sys import *
from heapq import *
from collections import defaultdict
import os, sys
from io import IOBase, BytesIO
M = 10 ** 9 + 7

def pow(a, b):
	res = 1
	while b > 0:
		if b & 1:
			res *= a
		a *= a
		b >>= 1
	return res

def powmod(a, b, m):
	res = 1
	while b > 0:
		if b & 1:
			res = res * a % m
		a *= a
		b >>= 1
	return res

def inv(a, m):
	return powmod(a, m - 2, m)

def alldivisors(n):
	list = []
	arr = []
	for i in range(1, int(sqrt(n) + 1)):
		if n % i == 0:
			if n / i == i:
				arr += [i]
			else:
				arr += [i]
				list.append(n // i)
	arr += list[::-1]
	return arr

def primefactorisation(n):
	potentional_p = 3
	itog_list = defaultdict(int)
	if n % 2 == 0:
		itog_list[2] = 0
	while n % 2 == 0:
		n = n // 2
		itog_list[2] += 1
	while n - 1:
		if potentional_p > n ** 0.5:
			itog_list[n] += 1
			return itog_list
		while n % potentional_p == 0:
			n = n // potentional_p
			itog_list[potentional_p] += 1
		potentional_p += 2
	return itog_list

def main():
	t = int(input())
	for _ in range(t):
		(h, n) = list(map(int, input().split()))
		a = list(map(int, input().split()))
		s = '1'
		pval = h
		res = 0
		for i in range(1, n):
			cval = a[i]
			if s == '1':
				s = '11'
			elif s == '11' and pval - cval == 1:
				s = '1'
			elif s == '11' and pval - cval > 1:
				res += 1
				s = '11'
			pval = cval
		if s == '11' and a[-1] != 1:
			res += 1
		print(res)
BUFSIZE = 8192

class FastIO(BytesIO):
	newlines = 0

	def __init__(self, file):
		self._file = file
		self._fd = file.fileno()
		self.writable = 'x' in file.mode or 'w' in file.mode
		self.write = super(FastIO, self).write if self.writable else None

	def _fill(self):
		s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
		self.seek((self.tell(), self.seek(0, 2), super(FastIO, self).write(s))[0])
		return s

	def read(self):
		while self._fill():
			pass
		return super(FastIO, self).read()

	def readline(self):
		while self.newlines == 0:
			s = self._fill()
			self.newlines = s.count(b'\n') + (not s)
		self.newlines -= 1
		return super(FastIO, self).readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.getvalue())
			(self.truncate(0), self.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


for q in range(int(input())):
	(h, n) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr.append(0)
	ans = 0
	i = 1
	while i < n:
		if arr[i] - 1 == arr[i + 1]:
			i += 2
		else:
			ans += 1
			i += 1
	print(ans)


for i in range(1):
	for _ in range(int(input())):
		(h, n) = map(int, input().split())
		a = list(map(int, input().split()))
		a.append(0)
		an = 0
		i = 1
		while i < n:
			if a[i] + 1 - a[i + 1] == 2:
				i += 2
			elif a[i] + 1 - a[i + 1] > 2:
				i += 1
				an += 1
			else:
				i += 1
		print(an)


import sys
input = sys.stdin.buffer.readline
q = int(input())
for i in range(q):
	(h, n) = [int(item) for item in input().split()]
	a = [int(item) for item in input().split()] + [0, 0, 0]
	ans = 0
	itr = 0
	while a[itr] != 0:
		if a[itr] - a[itr + 1] <= 1 and a[itr + 1] - a[itr + 2] <= 1:
			itr += 2
		elif a[itr] - a[itr + 1] <= 1 and a[itr + 1] - a[itr + 2] > 1:
			a[itr + 1] = a[itr + 2] + 1
			ans += 1
			itr += 1
		elif a[itr] - a[itr + 1] > 1:
			a[itr] = a[itr + 1] + 1
	print(ans)


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	(h, n) = map(int, input().split())
	p = list(map(int, input().split())) + [0]
	n += 1
	p = p[::-1]
	ans = 0
	i = n - 1
	while True:
		if i <= 1:
			break
		if p[i - 1] + 1 < p[i]:
			p.pop()
			p.append(p[i - 1] + 1)
		elif p[i - 2] + 1 == p[i - 1]:
			p.pop()
			p.pop()
			i -= 2
		else:
			p.pop()
			ans += 1
			pi = p.pop()
			p.append(pi - 1)
			i -= 1
	print(ans)


from collections import deque
q = int(input())
for run in range(q):
	(h, n) = map(int, input().split())
	hs = deque(map(int, input().split()))
	s = set(hs)
	cur = hs.popleft()
	hs.append(0)
	cnt = 0
	while cur > 0:
		if cur <= 2:
			break
		lo = hs.popleft()
		if cur == lo + 1:
			cur = lo - 1
			if lo - 1 in s:
				hs.popleft()
			else:
				cnt += 1
		else:
			cur = lo + 1
			hs.appendleft(lo)
	print(cnt)


a = int(input())
l3 = []
for i in range(a):
	c = 0
	(h, n) = map(int, input().split())
	l1 = [int(a) for a in input().split()]
	r = l1[0]
	j = 1
	while r >= 1:
		if j < n:
			if r == l1[j] + 1:
				if j + 1 == n:
					if l1[j] >= 2:
						c += 1
						break
					else:
						break
				if r != l1[j + 1] + 2:
					c += 1
					r = r - 2
					j = j + 1
					continue
				else:
					r = r - 2
					j = j + 2
			else:
				r = l1[j] + 1
		else:
			break
	l3.append(c)
for j in range(a):
	print(l3[j])


def request():
	(h, n) = map(int, input().split())
	p = list(map(int, input().split()))
	c = 0
	i = 0
	while i < n - 1:
		if p[i] - p[i + 1] > 1:
			p[i] = p[i + 1] + 1
		if p[i + 1] + 1 == p[i]:
			if i + 2 >= n:
				if p[i] > 2:
					c += 1
			elif p[i + 2] + 1 != p[i + 1]:
				c += 1
				p[i + 1] -= 1
				i -= 1
			i += 1
		i += 1
	return c
for i in range(int(input())):
	print(request())


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
import bisect
for j in range(int(input())):
	(h, n) = map(int, input().split())
	sorts = list(map(int, input().split()))
	sorts.reverse()
	moves = 0
	current = sorts[-1]
	while current > 2:
		ind = bisect.bisect_left(sorts, current)
		if sorts[ind] >= current and ind != 0:
			ind -= 1
		h1 = sorts[ind]
		if current != sorts[ind]:
			current = h1 + 1
		if current <= 2:
			break
		if ind - 1 >= 0:
			if abs(sorts[ind - 1] - h1) == 1:
				current = sorts[ind - 1]
			else:
				moves += 1
				current = sorts[ind - 1] + 1
		elif current == sorts[0] or abs(current - sorts[0]) == 2:
			break
		else:
			moves += 1
			break
	print(moves)


import sys
import bisect as b
import math
from collections import defaultdict as dd
input = sys.stdin.readline
mo = 10 ** 9 + 7

def cin():
	return map(int, sin().split())

def ain():
	return list(map(int, sin().split()))

def sin():
	return input()

def inin():
	return int(input())

def computeGCD(x, y):
	while y:
		(x, y) = (y, x % y)
	return x
for i in range(inin()):
	(h, n) = cin()
	l = ain()
	x = h
	c = 0
	if h <= 2:
		print(0)
	else:
		i = 0
		l += [0, 0]
		while i < n:
			if x <= 2 or l[i] <= 2:
				break
			if l[i + 1] == x - 1:
				if l[i + 2] == x - 2:
					x = x - 2
					i += 2
				else:
					c += 1
					x = l[i + 2] + 1
					i += 1
			else:
				x = l[i + 1] + 1
		print(c)


for _ in range(int(input())):
	(h, n) = [int(a) for a in input().split()]
	p = list(map(int, input().split()))
	ans = 0
	p = [0] + p
	v = [0] * (n + 2)
	for i in range(1, n + 1):
		v[i] = p[i]
	v.append(0)
	i = 2
	while i <= n:
		if v[i] - 1 == v[i + 1]:
			i += 1
		else:
			ans += 1
		i += 1
	print(ans)


for tc in [0] * int(input()):
	(h, n) = map(int, input().split())
	p = list(map(int, input().split()))
	p.append(0)
	x = 1
	c = 0
	while x < n:
		if p[x] - p[x + 1] >= 2:
			c += 1
			x += 1
		else:
			x += 2
	print(c)


import sys
readline = sys.stdin.readline
t = int(readline())
for _ in range(t):
	(h, n) = map(int, readline().split())
	tmp = list(map(int, readline().split()))
	i = 0
	c = 0
	while i < n:
		if i < n - 2:
			if tmp[i + 1] - tmp[i + 2] == 1:
				i += 1
			else:
				c += 1
		elif i == n - 2:
			if tmp[i + 1] == 1:
				break
			else:
				c += 1
				break
		else:
			break
		i += 1
	print(c)


q = int(input())
for _ in range(q):
	(h, n) = map(int, input().split())
	p = list(map(int, input().split()))[1:]
	dangers = []
	rows = 1
	i = 0
	while i < len(p):
		if i > 0 and p[i] == p[i - 1] - 1:
			rows += 1
		else:
			rows = 1
		if (i == len(p) - 1 or p[i + 1] != p[i] - 1) and p[i] > 1:
			if rows % 2:
				dangers.append(p[i])
		i += 1
	print(len(dangers))


tc = int(input())
while tc > 0:
	(h, n) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	i = 0
	s = 0
	arr = []
	while i < n:
		if i > 0 and a[i] != a[i - 1] - 1:
			arr.append(False)
			s += 1
		arr.append(True)
		i += 1
		s += 1
	if a[-1] != 1:
		arr.append(False)
		s += 1
	h = s
	dp = [10 ** 10] * h
	dp[0] = 0
	for i in range(h - 1):
		a = 0
		if not arr[i + 1]:
			a = 0
		else:
			a = 1
		dp[i + 1] = min(dp[i + 1], a + dp[i])
		if i + 2 < h:
			if not arr[i + 2]:
				if not arr[i + 1]:
					a = 2
				else:
					a = 1
			elif not arr[i + 1]:
				a = 1
			else:
				a = 0
			dp[i + 2] = min(dp[i + 2], a + dp[i])
	if h - 2 >= 0:
		if arr[h - 1]:
			print(min(dp[h - 2], dp[h - 1]))
		else:
			print(min(dp[h - 2] + 1, dp[h - 1]))
	else:
		print(dp[h - 1])
	tc -= 1


from collections import defaultdict
for _ in range(int(input())):
	(h, n) = map(int, input().split())
	mov = list(map(int, input().split()))
	i = h
	ans = 0
	dp = [0 for i in range(n)]
	for i in range(n - 2, -1, -1):
		if mov[i] <= 2 or mov[i + 1] <= 1:
			dp[i] = 0
		elif i + 2 < n and mov[i + 1] - mov[i + 2] == 1:
			dp[i] = min(dp[i + 2], 1 + dp[i + 1])
		else:
			dp[i] = 1 + dp[i + 1]
	print(dp[0])


q = int(input())
for _ in range(q):
	(h, n) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr.pop(0)
	arr.append(0)
	curr = h
	ans = 0
	index = 0
	while index < n - 1:
		if arr[index] - arr[index + 1] > 1:
			ans += 1
		else:
			index += 1
		index += 1
	print(ans)


for _ in range(int(input())):
	(h, n) = map(int, input().split())
	p = list(map(int, input().split()))
	xyz = set(p)
	ans = 0
	for i in p:
		if i < h:
			h = i + 1
		if h <= 2:
			break
		if i == h - 1:
			if h - 2 in xyz:
				h -= 2
			else:
				ans += 1
				h -= 2
	print(ans)


q = int(input())
for i in range(q):
	(h, n) = map(int, input().split())
	p = [int(i) for i in input().split()]
	now = p[0]
	index = 0
	p = p[1:]
	p.append(0)
	ans = 0
	while index < n - 1:
		if now - p[index] == 1 and p[index] - p[index + 1] == 1:
			now = p[index + 1]
			index += 2
		elif now - p[index] == 1 and p[index] - p[index + 1] != 1:
			now = p[index] - 1
			index += 1
			ans += 1
		else:
			now = p[index] + 1
	print(ans)


import os
from io import BytesIO, IOBase
import sys
from collections import defaultdict, deque, Counter
from bisect import *
from math import sqrt, pi, ceil, log, inf, gcd
from itertools import permutations
from copy import deepcopy
from heapq import *
from sys import setrecursionlimit

def main():
	for _ in range(int(input())):
		(h, n) = map(int, input().split())
		a = list(map(int, input().split()))
		a.append(0)
		ans = 0
		i = 1
		while i < n:
			if a[i] + 1 - a[i + 1] == 2:
				i += 2
			elif a[i] + 1 - a[i + 1] > 2:
				i += 1
				ans += 1
			else:
				i += 1
		print(ans)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


for t in range(int(input())):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	a.append(0)
	if m == 1:
		print(0)
		continue
	b = []
	for i in range(m):
		b.append(a[i] - a[i + 1])
	i = 0
	count = 0
	while i < m - 1:
		if b[i + 1] == 1:
			i += 2
		elif b[i + 1] > 1:
			count += 1
			i += 1
	print(count)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import factorial
from collections import Counter, defaultdict
from heapq import heapify, heappop, heappush

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

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

def N():
	return int(input())

def comb(n, m):
	return factorial(n) / (factorial(m) * factorial(n - m)) if n >= m else 0

def perm(n, m):
	return factorial(n) // factorial(n - m) if n >= m else 0

def mdis(x1, y1, x2, y2):
	return abs(x1 - x2) + abs(y1 - y2)
mod = 1000000007
INF = float('inf')

def main():
	for _ in range(N()):
		(h, n) = RL()
		arr = RLL()
		arr.append(-1000)
		res = 0
		now = h
		tag = 1
		while now > 2:
			if tag < n and now - 1 == arr[tag]:
				if tag + 1 < n and now - 2 == arr[tag + 1]:
					now -= 2
					tag += 2
				else:
					now -= 1
					tag += 1
					res += 1
			else:
				now = arr[tag] + 1
		print(res)
main()


q = int(input())
for i in range(q):
	inp = input()
	inp_arr = inp.split(' ')
	h = int(inp_arr[0])
	n = int(inp_arr[1])
	inp_p = input()
	inp_p_arr = inp_p.split(' ')
	inp_p_arr = [int(j) for j in inp_p_arr]
	inp_p_arr.append(0)
	count = 0
	par_che = 1
	for j in range(1, n):
		if inp_p_arr[j] - inp_p_arr[j + 1] == 1:
			par_che += 1
		else:
			if par_che % 2 == 1:
				count += 1
			par_che = 1
	print(count)


for _ in range(int(input())):
	(h, n) = map(int, input().split())
	(*a,) = map(int, input().split())
	(ans, c) = (0, 0)
	for i in range(1, n):
		if a[i] == a[i - 1] - 1:
			c += 1
		else:
			if c % 2:
				ans += 1
			c = 1
	if c % 2 and a[-1] - 1:
		ans += 1
	print(ans)


import sys
import math
from collections import defaultdict
t = int(sys.stdin.readline())
for _ in range(t):
	dp = defaultdict(int)
	(h, n) = map(int, sys.stdin.readline().split())
	l = list(map(int, sys.stdin.readline().split()))
	for i in range(n):
		dp[l[i]] = 1
	i = h
	(ans, j) = (0, 0)
	while i > 2:
		if dp[i - 1] == 1 and dp[i - 2] == 1:
			i -= 2
			continue
		if dp[i - 1] == 1:
			ans += 1
			i -= 2
			continue
		if j >= n:
			break
		while j < n:
			if l[j] < i:
				i = l[j] + 1
				break
			else:
				j += 1
	print(ans)


from sys import stdin
t = int(input())
while t > 0:
	count = 0
	(n, m) = [int(i) for i in stdin.readline().split()]
	a = [int(i) for i in stdin.readline().split()]
	d = {i: 1 for i in a}
	curr = a[0]
	i = 0
	while curr > 0 and i < m:
		if curr <= 2:
			break
		elif d.get(curr - 1, -1) != -1 and d.get(curr - 2, -1) != -1:
			curr -= 2
			i += 2
		elif d.get(curr - 1, -1) != -1:
			count += 1
			i += 1
			curr -= 1
		elif i + 1 < m:
			curr = a[i + 1] + 1
		else:
			curr = 0
	print(count)
	t -= 1


q = int(input())
for i in range(q):
	(h, n) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()] + [10 ** 10]
	counter = 0
	arr = 0
	for i in range(1, n + 1):
		if a[i] == a[i - 1] - 1:
			counter += 1
		else:
			if counter % 2 == 1 and a[i - 1] != 1:
				arr += 1
			counter = 1
	print(arr)


import sys
readline = sys.stdin.readline
Q = int(readline())
inf = 10 ** 9
Ans = [None] * Q
for qu in range(Q):
	(H, N) = map(int, readline().split())
	P = list(map(int, readline().split()))
	ans = 0
	cur = P[0]
	curidx = 0
	step = set(P)
	while True:
		if cur <= 2:
			break
		if curidx >= N - 1:
			break
		if P[curidx + 1] + 1 <= 2:
			break
		if P[curidx + 1] - 1 in step:
			curidx += 2
			cur = P[curidx]
		else:
			ans += 1
			curidx += 1
			cur = P[curidx] - 1
	Ans[qu] = ans
print('\n'.join(map(str, Ans)))


import sys
tmp = sys.stdin.readline()
noq = int(tmp)
while noq:
	noq -= 1
	tmp = sys.stdin.readline().split()
	H = int(tmp[0])
	n = int(tmp[1])
	tmp = sys.stdin.readline().split()
	state = 0
	last = 0
	ans = 0
	for i in range(1, n):
		cur = int(tmp[i])
		if not state:
			state = 1
		elif last - cur > 1:
			ans += 1
			state = 1
		else:
			state = 0
		last = cur
	if state and last > 1:
		ans += 1
	print(ans)


queries = int(input())
for q in range(queries):
	h_n = [int(i) for i in input().split()]
	P = [int(i) for i in input().split()]
	P.append(0)
	result = 0
	i = 1
	while i < h_n[1]:
		if P[i] == P[i + 1] + 1:
			i += 2
		else:
			i += 1
			result += 1
	print(result)