There are $n$ houses numbered from $1$ to $n$ on a circle. For each $1 \leq i \leq n - 1$, house $i$ and house $i + 1$ are neighbours; additionally, house $n$ and house $1$ are also neighbours.

Initially, $m$ of these $n$ houses are infected by a deadly virus. Each morning, Cirno can choose a house which is uninfected and protect the house from being infected permanently.

Every day, the following things happen in order:

Cirno chooses an uninfected house, and protect it permanently.

All uninfected, unprotected houses which have at least one infected neighbor become infected.

Cirno wants to stop the virus from spreading. Find the minimum number of houses that will be infected in the end, if she optimally choose the houses to protect.

Note that every day Cirno always chooses a house to protect before the virus spreads. Also, a protected house will not be infected forever.


-----Input-----

The input consists of multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. Description of test cases follows.

The first line of each test case consists of two positive integers $n, m$ ($5 \leq n \leq 10^9$, $1 \leq m \leq \min(n, 10^5)$) — the number of houses on the circle, and the number of houses that are initially infected.

The second line of each test case consists of $m$ distinct positive integers $a_1, a_2, \cdots , a_m$ ($1 \leq a_i \leq n$) — the indices of the houses infected initially.

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


-----Output-----

For each test case, output an integer on a separate line, which is the minimum number of infected houses in the end.


-----Examples-----

Input
8
10 3
3 6 8
6 2
2 5
20 3
3 7 12
41 5
1 11 21 31 41
10 5
2 4 6 8 10
5 5
3 2 5 4 1
1000000000 1
1
1000000000 4
1 1000000000 10 16
Output
7
5
11
28
9
5
2
15


-----Note-----

In the first test case:

At the start of the first day, house $3$, $6$, $8$ are infected. Choose house $2$ to protect.

At the start of the second day, house $3$, $4$, $5$, $6$, $7$, $8$, $9$ are infected. Choose house $10$ to protect.

At the start of the third day, no more houses are infected.

In the second test case:

At the start of the first day, house $2$, $5$ are infected. Choose house $1$ to protect.

At the start of the second day, house $2$, $3$, $4$, $5$, $6$ are infected. No more available houses can be protected.

Difficulty: EASY
Tags: Sorting

Implementation

Greedy algorithms
Skill types: Sorting

Greedy algorithms

Starter code:

Solutions:
t = int(input())
result = []
for i in range(t):
	(n, m) = list(map(int, input().split(' ')))
	ai = list(map(int, input().split(' ')))
	ai.sort()
	nbrBetweenElements = [ai[k + 1] - ai[k] - 1 for k in range(m - 1)]
	nbrBetweenElements.append(n + ai[0] - ai[-1] - 1)
	nbrBetweenElements.sort()
	nbrBetweenElements.reverse()
	ind = 0
	nbrProtectedH = 0
	for ind in range(m):
		if nbrBetweenElements[ind] - 4 * ind == 1:
			nbrProtectedH += 1
			break
		elif nbrBetweenElements[ind] - 4 * ind > 1:
			nbrProtectedH += nbrBetweenElements[ind] - 4 * ind - 1
		else:
			break
	result.append(n - nbrProtectedH)
for i in result:
	print(i)


import sys
t = int(sys.stdin.readline())
for i in range(t):
	(n, m) = map(int, sys.stdin.readline().split())
	lst = list(map(int, sys.stdin.readline().split()))
	lst.sort()
	lst1 = []
	for j in range(m - 1):
		gap = lst[j + 1] - lst[j] - 1
		lst1.append(gap)
	a = n - lst[-1]
	b = lst[0] - 1
	lst1.append(a + b)
	lst1.sort(reverse=True)
	c = 0
	ans = 0
	for j in lst1:
		ele = j - c * 4
		c += 1
		if ele <= 0:
			break
		elif ele == 1:
			ans += 1
		else:
			ans += ele - 1
	print(n - ans)


import sys
input = sys.stdin.readline

def solve(n, m, a):
	a = sorted(a)
	a_diff = [a[i] - a[i - 1] - 1 for i in range(1, m)]
	a_diff.append(n - a[-1] + a[0] - 1)
	a_diff.sort(reverse=True)
	tm = 0
	non_infected = 0
	for a_i in a_diff:
		saved = 0
		if a_i - 2 * tm > 0:
			saved = max(1, a_i - 2 * tm - 1)
			non_infected += saved
		tm += 2
	return n - non_infected
t = int(input())
for _ in range(t):
	(n, m) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	print(solve(n, m, a))


import sys

def sol(n, m, a):
	a = sorted(a)
	rng = []
	for i in range(m):
		rng.append(n - (a[i - 1] - a[i]) % n - 1)
	rng = sorted(rng)
	saved = 0
	timer = 0
	for i in range(m):
		if rng[-i - 1] - timer > 0:
			saved += 1 + max(0, rng[-i - 1] - timer - 2)
			timer += 4
		else:
			break
	return n - saved

def main():
	f = sys.stdin
	t = int(f.readline())
	for _ in range(t):
		(n, m) = map(int, f.readline().split())
		a = list(map(int, f.readline().split()))
		ans = sol(n, m, a)
		print(ans)
main()


import sys

def solve():
	inp = sys.stdin.readline
	(n, m) = map(int, inp().split())
	a = list(map(int, inp().split()))
	a.sort()
	d = [None] * m
	for i in range(1, m):
		d[i] = a[i] - a[i - 1]
	d[0] = a[0] + n - a[-1]
	d.sort(reverse=True)
	x = 1
	r = m
	for i in range(m):
		if d[i] <= x:
			r += d[i] - 1
		elif d[i] == x + 1:
			r += x - 1
		else:
			r += x
		x += 4
	print(r)

def main():
	for i in range(int(sys.stdin.readline())):
		solve()
main()


def solve():
	(a, b) = map(int, input().split())
	(a, b) = (b, a)
	ret = 0
	cnt = 0
	lsa = list(map(int, input().split()))
	lsa.sort()
	lsb = []
	for i in range(a - 1):
		lsb.append(lsa[i + 1] - 1 - lsa[i])
	lsb.append(b - lsa[-1] - 1 + lsa[0])
	lsb.sort(reverse=True)
	for i in range(a):
		if lsb[i] <= cnt:
			break
		if cnt + 1 == lsb[i]:
			ret += 1
		else:
			ret += lsb[i] - cnt - 1
		cnt += 4
	print(b - ret)
t = int(input())
for i in range(t):
	solve()


x = int(input())

def cal(n, m, arr):
	if m == 1:
		return 2
	if m == n:
		return m
	arr.sort()
	p = [arr[0] + n - arr[-1] - 1]
	for i in range(1, m):
		p.append(arr[i] - arr[i - 1] - 1)
	p.sort(reverse=True)
	t = 0
	sd = 0
	i = 0
	while i < len(p):
		gd = p[i] - t * 2
		if gd <= 0:
			break
		if gd <= 2:
			t += 1
			sd += 1
		else:
			t += 2
			sd += gd - 1
		i += 1
	return n - sd
for jj in range(x):
	(n, m) = [int(i) for i in input().split(' ')]
	arr = [int(i) for i in input().split(' ')]
	print(cal(n, m, arr))


t = int(input())
ans = []
for _ in range(t):
	data = list(map(int, input().split()))
	(n, m) = (data[0], data[1])
	cntg = sorted(list(map(int, input().split())))
	rng = []
	for i in range(m):
		rng.append(n - (cntg[i - 1] - cntg[i]) % n - 1)
	rng.sort()
	saved = 0
	timer = 0
	for i in range(m):
		if rng[-i - 1] - timer > 0:
			saved += 1 + max(0, rng[-i - 1] - timer - 2)
			timer += 4
		else:
			break
	ans.append(n - saved)
for i in range(t):
	print(ans[i])


import sys
R = lambda : map(int, next(sys.stdin).split())
(t,) = R()
while t:
	t -= 1
	(n, m) = R()
	(*a,) = R()
	a.sort()
	distance = []
	for i in range(m - 1):
		distance.append(a[i + 1] - a[i] - 1)
	distance.append(n - a[-1] + a[0] - 1)
	distance.sort(reverse=True)
	day = 0
	cnt = 0
	for x in distance:
		if x > 2 * day:
			x -= 2 * day
			cnt += 1
			day += 1
			if x - 2 > 0:
				cnt += x - 2
				day += 1
		else:
			break
	print(n - cnt)


def main():
	for t in range(int(input())):
		(n, m) = map(int, input().split())
		a = sorted(list(map(int, input().split())))
		x = []
		for i in range(m - 1):
			x.append(a[i + 1] - a[i] - 1)
		x.append(n - a[m - 1] + a[0] - 1)
		x.sort(reverse=True)
		(cnt, d) = (0, 0)
		for i in range(len(x)):
			x[i] -= d * 2
			if x[i] <= 0:
				break
			if x[i] > 2:
				cnt += x[i] - 1
				d += 2
			else:
				cnt += 1
				d += 1
		print(n - cnt)
main()


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	if m == 1:
		print(2)
	else:
		a.sort()
		b = [a[i] - a[i - 1] - 1 for i in range(1, m)]
		b.append(a[0] + n - a[-1] - 1)
		b.sort(reverse=True)
		s = 0
		for i in range(m):
			b[i] -= 4 * i
			if b[i] > 0:
				if b[i] == 1:
					s += 1
				else:
					s += b[i] - 1
			else:
				break
		print(n - s)


from sys import stdin
for _ in range(int(stdin.readline().strip())):
	(houses, infected) = list(map(int, stdin.readline().strip().split()))
	virus = list(map(int, stdin.readline().strip().split()))
	virus.sort()
	distancias = [houses - virus[-1] + virus[0] - 1]
	for i in range(len(virus) - 1):
		distancias.append(virus[i + 1] - virus[i] - 1)
	distancias.sort(reverse=True)
	total = 0
	for i in range(len(distancias)):
		distancias[i] = distancias[i] - 4 * i - 1
		if distancias[i] == 0:
			distancias[i] = 1
		if distancias[i] < 0:
			break
		total += distancias[i]
	print(houses - total)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	lg = [a[i + 1] - a[i] - 1 for i in range(m - 1)]
	lg.append(n - (a[-1] - a[0] + 1))
	lg.sort(reverse=True)
	ct = 1
	ans = 0
	for x in lg:
		if x - ct <= 0:
			ans += x - ct == 0
			break
		else:
			ans += x - ct
			ct += 4
	print(n - ans)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = sorted(map(int, input().split()))
	seps = []
	for i in range(1, m):
		seps.append(a[i] - a[i - 1] - 1)
	seps.append(a[0] - 1 + n - a[-1])
	seps.sort()
	inf = 0
	protected = 0
	while seps and seps[-1] > inf:
		protected += max(1, seps.pop() - 1 - inf)
		inf += 4
	print(n - protected)


import sys
input = sys.stdin.readline
un = lambda : [*map(int, input().split())]
for _ in range(*un()):
	(n, m) = un()
	a = un()
	a.sort()
	b = []
	for i in range(m - 1):
		b.append(a[i + 1] - a[i] - 1)
	b.append(n - a[-1] + a[0] - 1)
	b.sort(reverse=True)
	gg = 0
	ans = 0
	for i in range(m):
		if b[i] - gg - 1 <= 0:
			if b[i] - gg - 1 == 0:
				ans += 1
			break
		ans += b[i] - gg - 1
		gg += 4
	print(n - ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = [0] + sorted(list(map(int, input().split())))
	b = []
	for i in range(1, len(a)):
		b.append(a[i] - a[i - 1] - 1)
	b[0] = b[0] + n - a[-1]
	b = sorted(b, reverse=True)
	days = 0
	count = 0
	for i in range(len(b)):
		z = b[i] - 2 * days
		if z == 1:
			count += 1
			days += 2
		elif z > 1:
			count += z - 1
			days += 2
		else:
			break
	print(n - count)


def solve(x, A):
	dp = []
	A = sorted(A)
	prev = -1
	for i in A:
		if prev == -1:
			prev = i
			continue
		if i - prev - 1 > 0:
			dp.append(i - prev - 1)
		prev = i
	if x - prev + A[0] - 1 > 0:
		dp.append(x - prev + A[0] - 1)
	Q = sorted(dp, reverse=True)
	ans = len(A)
	cur = 0
	for (i, v) in enumerate(Q):
		if v - cur == 1:
			ans += v - 1
		elif v > cur:
			ans += 1 + cur
		else:
			ans += v
		cur += 4
	return ans

def read():
	s = input().strip('\n').split(' ')
	(n, x) = (int(s[0]), int(s[1]))
	s = input().strip('\n').split(' ')
	A = [int(x) for x in s]
	return (n, A)

def main():
	n = int(input())
	for _ in range(n):
		(x, A) = read()
		res = solve(x, A)
		print(res)
		pass
	pass
main()


n = int(input())
for e in range(n):
	l1 = list(map(int, input().split()))
	l2 = list(map(int, input().split()))
	l2.sort()
	a = []
	for i in range(len(l2) - 1):
		a.append(l2[i + 1] - l2[i] - 1)
	a.append(l1[0] - l2[-1] + l2[0] - 1)
	a.sort(reverse=True)
	p = 0
	c = 0
	for i in range(len(a)):
		q = a[i] - 2 * p
		if q == 1:
			c += 1
			break
		elif q <= 0:
			break
		else:
			c += q - 1
			p += 2
	print(l1[0] - c)


t = int(input())
for x in range(t):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	gaps = [a[i + 1] - a[i] - 1 for i in range(m - 1)]
	gap = n - (a[-1] - a[0] + 1)
	gaps.append(gap)
	gaps.sort(reverse=True)
	(prot, inf) = (0, 0)
	for gap in gaps:
		gap -= inf
		if gap <= 0:
			break
		if gap <= 2:
			prot += 1
			inf += 2
		else:
			prot += gap - 1
			inf += 4
	print(n - prot)


import math

def slove():
	(a, b) = map(int, input().split())
	c = list(map(int, input().split()))
	c.sort()
	opop = []
	for i in range(len(c) - 1):
		opop.append(c[i + 1] - c[i] - 1)
	opop.append(a - c[-1] + c[0] - 1)
	opop.sort(reverse=True)
	y = 0
	ans = 0
	for i in range(len(opop)):
		if opop[i] - 2 * y <= 0:
			break
		elif opop[i] - y * 2 <= 2:
			ans += 1
			y += 1
		else:
			ans += opop[i] - 2 * y - 1
			y += 2
	print(a - ans)
for i in range(int(input())):
	slove()


def main():
	t = int(input())
	while t:
		t -= 1
		(n, m) = list(map(int, input().split()))
		a = list(map(int, input().split()))
		a = sorted(a)
		distance = []
		for i in range(len(a) - 1):
			distance.append(a[i + 1] - a[i] - 1)
		distance.append(a[0] - a[m - 1] + n - 1)
		distance = sorted(distance)
		r = 0
		ans = 0
		while distance:
			top = distance.pop()
			if top - r * 2 > 0:
				ans += max(1, top - r * 2 - 1)
			r += 2
		print(n - ans)
main()


def main():
	for _ in range(int(input())):
		(n, m) = map(int, input().split())
		tab = list(map(int, input().split()))
		tab.sort(reverse=1)
		kraw = [0] * (m + 1)
		odj = 1
		for i in range(m - 1):
			kraw[i] = tab[i] - tab[i + 1] - 1
		kraw[m - 1] = n - tab[0] + (tab[-1] - 1)
		kraw.sort(reverse=1)
		i = 0
		while odj < kraw[i]:
			n -= kraw[i] - odj
			odj += 4
			i += 1
		if odj == kraw[i]:
			n -= 1
		print(n)
main()


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = sorted([int(i) for i in input().split()])
	if m == 1:
		print(2)
		continue
	b = []
	for i in range(1, m):
		b.append(abs(a[i] - a[i - 1]) - 1)
	b.append(n - a[-1] + a[0] - 1)
	b.sort(reverse=1)
	(inf, d) = (0, 0)
	for k in b:
		dd = d * 2
		if dd >= k:
			inf += k
			continue
		inf += dd
		if k - dd >= 2:
			inf += 1
			d += 2
		else:
			d += 1
	print(inf + m)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	b = []
	for i in range(m - 1):
		b.append(a[i + 1] - a[i] - 1)
	b.append(n - a[-1] + a[0] - 1)
	b.sort(reverse=True)
	i = 1
	if b[0] == 1:
		ans = 1
	elif b[0] == 0:
		ans = 0
	else:
		ans = b[0] - 1
		while i < m and b[i] - 4 * i - 1 > 0:
			ans += b[i] - 4 * i - 1
			i += 1
		if i < m and b[i] > 4 * i:
			ans += 1
	print(n - ans)


case = int(input())
for i in range(case):
	(n, m) = (int(v) for v in input().split())
	a = [int(v) for v in input().split()]
	a.sort()
	b = []
	move = 0
	safe = 0
	for j in range(m - 1):
		b.append(a[j + 1] - a[j] - 1)
	b.append(a[0] + n - a[m - 1] - 1)
	b.sort(reverse=True)
	for k in range(m):
		x = b[k] - 2 * move
		if x >= 3:
			move += 2
			safe += x - 1
		elif x >= 1:
			move += 1
			safe += 1
		else:
			pass
	print(n - safe)


from typing import List
from collections import defaultdict
import heapq

class Solution:

	def solve(self, n, m, a):
		hp = []
		a.sort()
		for i in range(1, m):
			hp.append(-(a[i] - a[i - 1] - 1))
		left = 0 if a[0] == 1 else a[0] - 1
		right = 0 if a[-1] == n else n - a[-1]
		if left + right:
			hp.append(-(left + right))
		heapq.heapify(hp)
		ans = 0
		timer = 0
		while hp:
			val = -heapq.heappop(hp) - 2 * timer
			if val <= 0:
				break
			if val == 1:
				ans += 1
				break
			ans += val - 1
			timer += 2
		return n - ans
obj = Solution()
T = int(input())
for _ in range(T):
	(n, m) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	ans = obj.solve(n, m, a)
	print(ans)


def cal(a, n, m):
	k = []
	i = 0
	a.sort()
	for j in a:
		dif = j - i - 1
		k.append(dif)
		i = j
	dif = n - i
	k[0] = k[0] + dif
	k.sort(reverse=True)
	opt = 0
	f = 0
	ans = 0
	while len(k) != 0 and f == 0:
		c = k.pop(0)
		c -= 2 * opt
		if c > 0:
			if c == 1:
				ans += c
			else:
				ans += c - 1
			opt += 2
		else:
			f = 1
	return n - ans
T = int(input())
for _ in range(T):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	print(cal(a, n, m))


import sys, os
if os.getlogin() == 'arun':
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
from collections import defaultdict
from math import comb
import math
t = int(input())

def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
for _ in range(t):
	(n, m) = map(int, input().split())
	lt = list(map(int, input().split()))
	lt.sort()
	l2 = []
	if m > 1:
		for i in range(m - 1):
			k = lt[i + 1] - lt[i] - 1
			if k > 0:
				l2.append(k)
		l2.append(lt[0] - 1 + n - lt[-1])
	else:
		l2 = [n - 1]
	l2.sort(reverse=True)
	count = 0
	ans = 0
	for x in l2:
		if x - 2 * count >= 3:
			ans += x - 2 * count - 1
			count += 2
		elif x - 2 * count >= 1:
			count += 1
			ans += 1
		else:
			break
	print(n - ans)


def ss(n, l):
	l = sorted(l)
	l.insert(0, 0)
	t = []
	for i in range(len(l) - 1):
		t.append(l[i + 1] - l[i] - 1)
	t[0] += n - l[-1]
	t = sorted(t)[::-1]
	x = 0
	ans = 0
	for i in t:
		y = i - 2 * x
		if y <= 0:
			break
		if y == 1:
			ans += 1
			x += 2
		else:
			ans += y - 1
			x += 2
	return n - ans
for _ in range(int(input())):
	(n, x) = map(int, input().split())
	l = list(map(int, input().split()))
	print(ss(n, l))


t = int(input())
while t:
	t -= 1
	(n, m) = map(int, input().split(' '))
	arr = [0] * m
	(*pos,) = map(int, input().split(' '))
	pos.sort(reverse=True)
	areas = list()
	for h in range(len(pos) - 1):
		areas.append(pos[h] - pos[h + 1] - 1)
	areas.append(n - pos[0] + pos[-1] - 1)
	areas.sort()
	day = 0
	count = 0
	for i in range(len(areas)):
		val = areas.pop() - 2 * day - 1
		if val == 0:
			val = 1
		if val > 0:
			count += val
			day += 2
			continue
		break
	print(n - count)


t = int(input())
arr = []
for j in range(0, t):
	(n, m) = list(map(int, input().split()))
	arr = sorted(list(map(int, input().split())))
	arr2 = []
	arr2.append(arr[0] + n - 1 - arr[m - 1])
	for i in range(1, m):
		arr2.append(arr[i] - arr[i - 1] - 1)
	arr2 = sorted(arr2, reverse=True)
	k = 0
	l = 0
	for s in range(0, len(arr2)):
		if arr2[s] - l > 3:
			k += arr2[s] - l - 1
			l += 4
		elif arr2[s] - l == 3:
			k += 2
			break
		elif 0 < arr2[s] - l < 3:
			k += 1
			break
		else:
			break
	print(sum(arr2) - k + m)


testcases = int(input())
for _ in range(testcases):
	(n1, x1) = input().split()
	n = int(n1)
	x = int(x1)
	a1 = input().split()
	a = [int(i) for i in a1]
	a.sort()
	l = []
	for i in range(0, x - 1):
		l.append(a[i + 1] - a[i] - 1)
	l.append(n - a[x - 1] + a[0] - 1)
	l.sort(reverse=True)
	ans = 0
	for i in range(len(l)):
		c = l[i] - i * 4 - 1
		if c < 0:
			break
		if c == 0:
			ans += 1
			break
		ans += c
	print(n - ans)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = [int(i) for i in input().split()]
	b = []
	a.sort()
	for i in range(1, m):
		b.append(a[i] - a[i - 1] - 1)
	b.append(n - a[-1] + a[0] - 1)
	b.sort()
	days = 0
	save = 0
	for i in range(len(b) - 1, -1, -1):
		if b[i] - days * 2 - 1 < 0:
			break
		elif b[i] - days * 2 - 1 == 0:
			save += 1
			break
		save += b[i] - days * 2 - 1
		days += 2
	print(n - save)


t = int(input())
sol = []
for _ in range(t):
	(n, m) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	a.sort()
	diff = [-1 for _ in range(m)]
	for i in range(m - 1):
		diff[i] = a[i + 1] - a[i] - 1
	diff[m - 1] = (n + a[0] - a[-1] - 1) % n
	diff.sort(reverse=True)
	infected = m
	for i in range(m):
		pre_inf = 4 * i
		if pre_inf >= diff[i]:
			infected += diff[i]
		elif pre_inf <= diff[i] - 2:
			infected += pre_inf + 1
		else:
			infected += pre_inf
	sol.append(infected)
for s in sol:
	print(s)


def get_holes(m, infected):
	g = []
	infected.sort()
	for i in range(len(infected) - 1):
		g.append(infected[i + 1] - infected[i] - 1)
	g.append(m - infected[-1] + infected[0] - 1)
	return g

def solve(n, m, infected):
	h = get_holes(m, infected)
	h.sort(reverse=True)
	k = 0
	protected = 0
	inf = 0
	for k in range(len(h)):
		r = h[k] - inf
		protected += r - 1 if r > 1 else 1 if r == 1 else 0
		inf += 4
	return n - protected
t = int(input())
for i in range(t):
	sizes = input().split()
	n = int(sizes[0])
	m = int(sizes[0])
	infected = [int(e) for e in input().split()]
	print(solve(n, m, infected))


import math
from collections import *

def solve():
	(n, m) = map(int, input().split())
	a = [int(i) for i in input().split()]
	t = []
	a.sort()
	for i in range(m - 1):
		t.append(a[i + 1] - a[i] - 1)
	t.append(a[0] - 1 + n - a[-1])
	t.sort(reverse=True)
	ans = 0
	l = -1
	for i in range(len(t)):
		if t[i] + l >= 0:
			if t[i] + l == 0:
				ans += 1
			ans += t[i] + l
		else:
			break
		l = l - 4
	print(n - ans)
t = int(input())
for _ in range(t):
	solve()


def num():
	c = int(input())
	return c

def stri():
	c = str(input())
	return c

def vector():
	c = list(map(int, input().split()))
	return c

def strvector():
	c = list(map(str, input().split()))
	return c
from heapq import heappop, heappush
import math

def isprime(num):
	a = 2
	while a <= math.sqrt(num):
		if num % a < 1:
			return False
		a = a + 1
	return num > 1
t = num()
while t > 0:
	t -= 1
	(n, m) = vector()
	arr = vector()
	arr.sort()
	if m == 1:
		print(2 if n >= 2 else 1)
		continue
	if n == m:
		print(m)
		continue
	h = []
	for i in range(1, m):
		heappush(h, -arr[i] + arr[i - 1] + 1)
	heappush(h, -(arr[0] + n - arr[-1] - 1))
	cnt = 0
	saved = 0
	while h:
		x = -heappop(h)
		if x - cnt <= 0:
			continue
		elif x - cnt > 2:
			saved += x - cnt - 1
			cnt += 4
		else:
			saved += 1
			cnt += 2
	print(n - saved)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = [int(i) for i in input().split()]
	a.sort()
	b = [n - a[-1] + a[0] - 1]
	for i in range(m - 1):
		b += [a[i + 1] - a[i] - 1]
	b.sort(reverse=True)
	(t, o) = (0, 0)
	for i in b:
		if i - t >= 3:
			o += i - t - 1
			t += 4
		elif i - t >= 1:
			o += 1
			t += 2
	print(n - o)


import heapq
for _ in range(int(input())):
	(n, m) = [int(i) for i in input().split()]
	arr = [int(i) for i in input().split()]
	gaps = [0] * m
	arr.sort()
	for i in range(len(arr) - 1):
		gaps[i] = arr[i + 1] - arr[i] - 1
	gaps[-1] = n + arr[0] - arr[-1] - 1
	gaps.sort(reverse=True)
	ans = 0
	d = 0
	for i in range(m):
		gaps[i] = gaps[i] - 2 * d
		if gaps[i] < 1:
			break
		if gaps[i] <= 2:
			ans += 1
			d += 1
		else:
			d += 2
			ans += gaps[i] - 1
	print(n - ans)


t = int(input())

def noOfInfected(n, m, l):
	l.sort()
	(diff, infected, uninfected, index) = ([], 0, 0, -1)
	for i in range(len(l)):
		if i > 0:
			diff.append(l[i] - l[i - 1] - 1)
		else:
			diff.append(l[i] - 1)
	diff[0] += n - l[-1]
	diff.sort(reverse=True)
	for i in range(len(diff)):
		if infected >= diff[i] or diff[i] == 0:
			break
		diff[i] -= infected
		if diff[i] > 1:
			diff[i] -= 1
		infected += 4
		uninfected += diff[i]
		index += 1
	if index > -1:
		return n - sum(diff[0:index + 1])
	return n
while t:
	(n, m) = list(map(int, input().split()))
	l = list(map(int, input().split()))
	print(noOfInfected(n, m, l))
	t -= 1


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr.sort()
	arr1 = []
	for i in range(0, m - 1):
		arr1.append(arr[i + 1] - arr[i] - 1)
	arr1.append(n - arr[m - 1] + arr[0] - 1)
	arr1.sort(reverse=True)
	ans = 0
	flag = True
	time = 0
	i = 0
	while flag and i < m:
		ele = arr1[i] - time * 2
		if ele <= 0:
			flag = False
		elif ele == 1:
			ans += 1
			flag = False
		else:
			ans += ele - 1
			i += 1
			time += 2
	print(n - ans)


for i in range(int(input())):
	(a, b) = input().split(' ')
	num_h = int(a)
	num_f = int(b)
	infected = [int(x) for x in input().split(' ')]
	infected.sort()
	if num_h == num_f:
		print(num_h)
	else:
		list_u = []
		for i in range(num_f - 1):
			list_u.append(infected[i + 1] - infected[i] - 1)
		list_u.append(infected[0] + (num_h - infected[-1]) - 1)
		list_u.sort()
		protected = 0
		protect = 1
		days = 0
		while protect <= len(list_u) and list_u[-protect] - days * 2 > 0:
			if list_u[-protect] - days * 2 == 1 or list_u[-protect] - days * 2 == 2:
				protected += 1
				days += 1
			else:
				protected += list_u[-protect] - days * 2 - 1
				days += 2
			protect += 1
		num_infect = num_h - protected
		print(num_infect)


t = int(input())

def solve():
	(n, m) = map(int, input().split())
	lst = list(map(int, input().split()))
	lst.sort()
	arr = []
	for i in range(1, m):
		arr += [lst[i] - lst[i - 1] - 1]
	arr += [lst[0] + n - lst[-1] - 1]
	arr.sort(reverse=True)
	t = 0
	saved = 0
	for i in range(m):
		arr[i] = arr[i] - 2 * t
		if arr[i] > 2:
			saved += arr[i] - 1
			t += 2
		elif arr[i] == 1:
			saved += 1
			t += 1
		elif arr[i] == 2:
			saved += 1
			t += 1
	print(n - saved)
while t:
	solve()
	t -= 1


import math
import collections
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort()
	ans = []
	for i in range(1, m):
		ans.append(l[i] - l[i - 1] - 1)
	ans.append(l[0] + n - l[-1] - 1)
	ans.sort(reverse=True)
	days = 0
	save = 0
	for i in ans:
		temp = i - 2 * days
		if temp <= 0:
			continue
		elif temp == 1:
			days += 1
			save += 1
		else:
			temp -= 1
			days += 2
			save += temp
	print(n - save)


n = int(input())
for i in range(n):
	(n_, m) = list(map(int, input().split()))
	arr = sorted(list(map(int, input().split())))
	arr_ = []
	arr_.append(n_ - arr[-1] + arr[0] - 1)
	for j in range(m - 1):
		arr_.append(arr[j + 1] - arr[j] - 1)
	arr_.sort(reverse=True)
	s = 0
	co = 0
	for j in arr_:
		if j >= 4 * co + 1:
			if j == 4 * co + 1:
				s += 1
			else:
				s += j - (4 * co + 1)
		else:
			break
		co += 1
	print(n_ - s)


for tcase in range(int(input())):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	d = [a[i] - a[i - 1] for i in range(m)]
	d[0] += n
	d.sort(reverse=True)
	ans = 0
	i = 0
	loop = True
	while i < m and loop and (d[i] - 2 - 4 * i >= 0):
		ans += max(d[i] - 2 - 4 * i, 1)
		loop = d[i] - 2 - 4 * i > 0
		i += 1
	print(n - ans)


t = int(input())
for i in range(t):
	(n, m) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	a = sorted(a)
	b = []
	for j in range(m - 1):
		b.append(abs(a[j] - a[j + 1]) - 1)
	c = abs(a[0] - 1) + abs(a[-1] - n)
	b.append(c)
	b = sorted(b, reverse=True)
	d = 0
	e = len(b)
	f = 0
	for k in range(e):
		g = b[k] - 2 * f
		if g == 1:
			d = d + g
			break
		elif g <= 0:
			break
		else:
			g = g - 1
			d = d + g
			f += 2
	print(n - d)


def solve():
	(n, m) = map(int, input().split())
	inf = [int(i) for i in input().split()]
	inf.sort()
	arr = [inf[0] - 1 + n - inf[-1]]
	for i in range(1, len(inf)):
		arr.append(inf[i] - inf[i - 1] - 1)
	arr.sort()
	ans = 0
	val = 0
	for i in range(len(arr) - 1, -1, -1):
		if arr[i] + val == 1:
			ans += 1
		else:
			ans += max(0, arr[i] + val - 1)
		val += -4
	print(n - ans)
t = int(input())
while t:
	t -= 1
	solve()


x = lambda : map(int, input().split())
(t,) = x()
for _ in '1' * t:
	(n, m) = x()
	a = sorted(x())
	d = []
	for i in range(m - 1):
		d.append(a[i + 1] - a[i] - 1)
	d.append(n - a[m - 1] + a[0] - 1)
	d.sort(reverse=True)
	cnt = 0
	dy = 0
	for y in d:
		if y > dy * 2:
			y -= dy * 2
			cnt += 1
			dy += 1
			if y - 2 > 0:
				cnt += y - 2
				dy += 1
		else:
			break
	print(n - cnt)


T = int(input())
for _ in range(T):
	(n, m) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort()
	ran = []
	for i in range(m - 1):
		ran.append(l[i + 1] - l[i] - 1)
	ran.append(n - l[-1] + (l[0] - 1))
	ran.sort()
	ran = ran[::-1]
	count = 0
	for i in range(len(ran)):
		x = ran[i] - i * 4
		if x > 0:
			if x == 1 or x == 2:
				count += 1
			else:
				count += x - 1
	print(n - count)


n = int(input())
for _ in range(n):
	h = input().split(' ')
	n = int(h[0])
	m = int(h[1])
	inf = [int(i) for i in input().split(' ')]
	inf.sort()
	spaces = [n - inf[-1] - 1 + inf[0]] + [inf[i] - inf[i - 1] - 1 for i in range(1, m)]
	spaces.sort(reverse=True)
	infected = m
	r = 0
	for x in spaces:
		q = x - 2 * r
		if q <= 0:
			infected += x
		elif q == 2:
			infected += 1 + 2 * r
		elif q == 1:
			infected += 2 * r
		else:
			infected += 1 + 2 * r
			r += 1
		r += 1
	print(infected)


for _ in range(int(input())):
	(n, m) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	a.sort()
	distances = []
	for i in range(1, m):
		distances.append(a[i] - a[i - 1] - 1)
	distances.append(n - a[-1] + (a[0] - 1))
	distances.sort(reverse=True)
	non_infected_houses = 0
	for i in range(0, len(distances)):
		if distances[i] - 4 * i - 1 < 0:
			break
		elif distances[i] - 4 * i - 1 == 0:
			non_infected_houses += 1
		non_infected_houses += distances[i] - 4 * i - 1
	print(n - non_infected_houses)


import math
from collections import defaultdict

def resolve(house_num, affect_house):
	section_num_list = []
	affect_house = sorted(affect_house)
	affect_len = len(affect_house)
	for index in range(affect_len - 1):
		a_section = affect_house[affect_len - 1 - index] - affect_house[affect_len - 1 - index - 1] - 1
		if a_section >= 1:
			section_num_list.append(a_section)
	section_last = affect_house[0] - 1 + house_num - affect_house[affect_len - 1]
	section_num_list.append(section_last)
	sorted_list = sorted(section_num_list, reverse=True)
	temp_max_index = 0
	save_num = 0
	day = 0
	while not sorted_list[temp_max_index] - day * 4 <= 0:
		sorted_list[temp_max_index] -= day * 4
		if sorted_list[temp_max_index] == 1:
			save_num += 1
		else:
			save_num += sorted_list[temp_max_index] - 1
		if temp_max_index == len(sorted_list) - 1:
			break
		else:
			temp_max_index += 1
			day += 1
	return house_num - save_num

def read_input():
	ints = input().split(' ')
	house_num = int(ints[0])
	affect_house = []
	lines_2 = input().split(' ')
	for item in lines_2:
		affect_house.append(int(item))
	return (house_num, affect_house)
case_num = int(input())
if not case_num == 0:
	for index in range(case_num):
		(house_num, affect_house) = read_input()
		res = resolve(house_num, affect_house)
		print(res)


t = int(input())
for ii in range(t):
	(n, m) = map(int, input().split())
	s = list(map(int, input().split()))
	s.sort()
	ll = []
	for i in range(1, m):
		ll.append(s[i] - s[i - 1] - 1)
	ll.append(s[0] + n - s[m - 1] - 1)
	ll.sort()
	ll = ll[::-1]
	i = 0
	x = 0
	ans = 0
	while i < len(ll):
		if ll[i] - x >= 1:
			if ll[i] - x <= 2:
				ans = ans + 1
			else:
				x = x + 2
				ans = ans + (ll[i] - x + 1)
			x = x + 2
		i = i + 1
	print(n - ans)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split(' '))
	a = list(map(int, input().split(' ')))
	a.sort()
	p = []
	for i in range(m - 1):
		p.append(abs(a[i + 1] - a[i]) - 1)
	if n - a[-1] + a[0] - 1 > 0:
		p.append(n - a[-1] + a[0] - 1)
	p.sort(reverse=True)
	infected = 0
	saved = 0
	for i in range(len(p)):
		p[i] -= infected
		if p[i] <= 0:
			continue
		if p[i] == 1 or p[i] == 2:
			saved += 1
			infected += 2
			continue
		saved += p[i] - 1
		infected += 4
	print(n - saved)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	L = list(map(int, input().split()))
	L.sort()
	M = []
	for i in range(1, m):
		a = L[i] - L[i - 1] - 1
		if a > 0:
			M.append(a)
	a = n - L[-1] + L[0] - 1
	if a > 0:
		M.append(a)
	M.sort(reverse=True)
	i = 0
	j = 0
	k = len(M)
	ans = 0
	while i < k:
		a = M[i]
		if a - 4 * j == 1:
			ans += 1
			i += 1
			j += 1
		elif a - 4 * j >= 1:
			ans += a - 4 * j - 1
			i += 1
			j += 1
		else:
			break
	print(n - ans)


for t in range(int(input())):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	L = []
	L.append(n - a[-1] + a[0] - 1)
	for i in range(m - 1):
		L.append(a[i + 1] - a[i] - 1)
	L.sort()
	left = 0
	sum = m
	for k in range(m):
		if L[k] <= 4 * (m - k - 1):
			sum += L[k]
		elif L[k] == 4 * (m - k - 1) + 1:
			sum += 4 * (m - k - 1)
		elif L[k] > 4 * (m - k - 1) + 1:
			sum += 4 * (m - k - 1) + 1
	print(sum)


from math import ceil
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = sorted(list(map(int, input().split())))
	b = [n - a[-1] + a[0] - 1]
	for i in range(m - 1):
		b += [a[i + 1] - a[i] - 1]
	b.sort(reverse=True)
	x = 0
	for i in range(m):
		b[i] = max(b[i] - 2 * x, 0)
		if b[i] == 0:
			continue
		elif b[i] == 1:
			x += 1
		elif b[i] == 2:
			b[i] -= 1
			x += 1
		else:
			b[i] -= 1
			x += 2
	else:
		print(n - sum(b))


for pratyush in range(int(input())):
	(n, m) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	(d, f, a) = ([0] * (m + 1), 0, [0] + a)
	a = [0] + sorted(a[1:])
	for i in range(2, m + 1):
		d[i] = a[i] - a[i - 1] - 1
	d[1] = a[1] - 1 + (n - a[m])
	d = [0] + sorted(d[1:], reverse=True)
	for i in range(1, m + 1):
		x = 2 * (i - 1)
		y = x * 2
		z = d[i] - y
		if z > 0:
			if z == 1 or z == 2:
				f += 1
			if z >= 3:
				f += d[i] - y - 1
	print(n - f)


import sys
input = sys.stdin.readline
result = []
t = int(input())
for _ in range(t):
	(n, x) = map(int, input().split())
	array = list(map(int, input().split()))

	def solve():
		array.sort()
		borderHouses = array[0] - 1 + (n - array[-1])
		newArr = [borderHouses]
		for i in range(len(array) - 1):
			(firstNum, secondNum) = (array[i], array[i + 1])
			newArr.append(secondNum - firstNum - 1)
		newArr.sort(reverse=True)
		count = 0
		(newCnt, halfCnt) = (0, 0)
		for num in newArr:
			newNum = max(num - newCnt * 4 - halfCnt * 2, 0)
			if newNum == 1:
				count += max(newNum, 0)
				halfCnt += 1
			else:
				count += max(newNum - 1, 0)
				newCnt += 1
		return n - count
	res = solve()
	print(res)


for _ in range(int(input())):
	(n, m) = list(map(int, input().split()))
	a = sorted(map(int, input().split()))
	b = []
	for i in range(1, m):
		if a[i] != a[i - 1] + 1:
			b += [a[i] - a[i - 1] - 1]
	if a[0] - 1 + n - a[-1] > 0:
		b += [a[0] - 1 + n - a[-1]]
	b = sorted(b)
	ans = 0
	for i in range(1, len(b) + 1):
		if b[-i] <= (i - 1) * 4:
			break
		if b[-i] <= (i - 1) * 4 + 2:
			ans += 1
			break
		ans += b[-i] - (i - 1) * 4 - 1
	print(n - ans)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr.sort()
	x = arr[0]
	for i in range(m - 1):
		arr[i] = arr[i + 1] - arr[i] - 1
	arr[m - 1] = n + x - arr[m - 1] - 1
	x = 0
	count = 0
	arr.sort(reverse=True)
	for i in range(m):
		if arr[i] - 2 * x > 2:
			count += arr[i] - 2 * x - 1
			x += 2
			arr[i] = 0
		elif arr[i] - 2 * x > 0:
			count += 1
			x += 1
			arr[i] = 0
	print(n - count)


for _ in range(int(input())):
	(n, x) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	a.sort()
	d = []
	for i in range(len(a)):
		if i != len(a) - 1:
			d.append(a[i + 1] - (1 + a[i]))
		else:
			d.append(n + a[0] - (a[i] + 1))
	d.sort(reverse=True)
	r = sum(d)
	p = 0
	for i in range(len(d)):
		if d[i] - i * 4 > 1:
			p += d[i] - (1 + i * 4)
		elif d[i] - i * 4 == 1:
			p += 1
			break
		else:
			break
	print(n - p)


for _ in range(int(input())):
	[m, n] = list(map(int, input().split()))
	a = list(map(int, input().split(' ')))
	a.sort()
	arr = []
	for i in range(len(a) - 1):
		arr.append(a[i + 1] - a[i] - 1)
	arr.append(m + a[0] - a[-1] - 1)
	arr.sort(reverse=True)
	ans = 0
	minus = 0
	while arr and arr[0] - minus > 0:
		ans += max(1, arr[0] - minus - 1)
		minus += 4 if arr[0] - minus > 2 else 2
		arr.pop(0)
	print(m - ans)


a = int(input())
for i in range(a):
	(n, m) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr.sort()
	gap = [0] * m
	for j in range(m - 1):
		gap[j] = arr[j + 1] - arr[j] - 1
	gap[m - 1] = n - arr[m - 1] + arr[0] - 1
	gap.sort(reverse=True)
	for k in range(len(gap)):
		gap[k] -= 4 * k + 1
	for l in range(len(gap)):
		if gap[l] < 0:
			gap[l] = 0
		elif gap[l] == 0:
			gap[l] = 1
	print(n - sum(gap))


import sys
input = sys.stdin.readline

def solve():
	(n, m) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr.sort()
	uninfected = []
	for i in range(m - 1):
		if arr[i + 1] - arr[i] - 1:
			uninfected.append(arr[i + 1] - arr[i] - 1)
	if arr[0] + n - arr[-1] - 1:
		uninfected.append(arr[0] + n - arr[-1] - 1)
	uninfected.sort(reverse=True)
	offset = ans = 0
	k = len(uninfected)
	for i in range(k):
		if uninfected[i] - offset == 1 or uninfected[i] - offset == 2:
			ans += 1
			offset += 2
		else:
			ans += max(uninfected[i] - 1 - offset, 0)
			offset += 4
	return n - ans
for _ in range(int(input())):
	print(solve())


import collections
import math
import sys
from queue import PriorityQueue

def main(testnumber):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	a = sorted(a)
	spaces = []
	space = a[0] - 1 + n - a[-1]
	if space > 0:
		spaces.append(space)
	for i in range(len(a) - 1):
		if a[i + 1] - a[i] - 1 > 0:
			spaces.append(a[i + 1] - a[i] - 1)
	spaces = sorted(spaces, reverse=True)
	saved = 0
	minus = 0
	for i in spaces:
		s = 0
		if i - minus * 2 > 0:
			s = 1
		s = max(s, i - minus * 2 - 1)
		if s > 0:
			saved += s
			minus += 1
		minus += 1
	print(n - saved)
t = int(input())
cnt = 1
while t > 0:
	main(cnt)
	cnt += 1
	t -= 1


import copy
t = int(input())
for tt in range(t):
	(n, m) = map(int, input().split())
	a = sorted([int(i) for i in input().split()])
	lens = []
	ans = copy.deepcopy(n)
	if m == 1:
		if n < 3:
			print(n)
		elif n == 3:
			print(1)
		else:
			print(2)
		continue
	for i in range(1, m):
		if a[i] - a[i - 1] > 1:
			lens.append(a[i] - a[i - 1] - 1)
	if n - a[-1] + a[0] - 1 > 0:
		lens.append(n - a[-1] + a[0] - 1)
	lens.sort(reverse=True)
	days = 0
	for val in lens:
		if val - days * 2 > 0:
			if val - days * 2 == 1:
				ans -= 1
				break
			if val - days * 2 == 2:
				ans -= 1
				days += 1
			else:
				ans -= val - days * 2 - 1
				days += 2
	print(ans)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr.sort()
	diff = []
	for i in range(m):
		if i == m - 1:
			diff.append(n - arr[i] + arr[0] - 1)
		else:
			diff.append(arr[i + 1] - arr[i] - 1)
	diff.sort(reverse=True)
	ans = 0
	for i in range(len(diff)):
		if i == 0:
			if diff[i] == 1:
				ans += 1
			elif diff[i] > 1:
				ans += diff[i] - 1
		elif diff[i] - 4 * i > 0:
			if diff[i] - 4 * i > 1:
				ans += diff[i] - 4 * i - 1
			else:
				ans += 1
	print(n - ans)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	dif = []
	for i in range(m):
		if i == m - 1:
			dif.append(n - a[i] + a[0] - 1)
			continue
		dif.append(a[i + 1] - a[i] - 1)
	dif.sort(reverse=True)
	res = 0
	inc = 0
	j = m - 1
	for i in range(m):
		if dif[i] - 4 * inc == 1:
			dif[i] = 1
			j = i
			break
		dif[i] = max(0, dif[i] - 4 * inc - 1)
		inc += 1
	for i in range(j + 1, m):
		dif[i] = 0
	print(n - sum(dif))


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort()
	a = []
	for i in range(m - 1):
		a.append(l[i + 1] - l[i] - 1)
	a.append(l[0] - 1 + n - l[-1])
	a.sort(reverse=True)
	ans = 0
	x = 0
	for i in range(len(a)):
		if a[i] - x - 1 == 0:
			ans += 1
			break
		else:
			ans += max(a[i] - x - 1, 0)
			x += 4
	print(n - ans)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	h = [a[0] - 1 + n - a[-1]]
	for i in range(1, m):
		h.append(a[i] - a[i - 1] - 1)
	h.sort(reverse=True)
	non = 0
	for i in range(m):
		non += max(0, h[i] - 4 * i - 1)
		if h[i] - 4 * i == 1:
			non += 1
	print(n - non)


import math
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	a = sorted(map(int, input().split()))
	intervals = [(a[i], a[i + 1]) for i in range(m - 1)]
	intervals.append((a[m - 1], n + a[0]))
	intervals.sort(key=lambda x: x[1] - x[0], reverse=True)
	days = 0
	count = m
	for (x, y) in intervals:
		nums = y - x - 1
		if nums == 0:
			continue
		if nums <= days << 1:
			count += nums
			continue
		left = nums - (days << 1)
		count += (days << 1) + (1 if left > 1 else 0)
		days += 2
	print(count)


t = int(input())
while t > 0:
	(n, m) = list(map(int, input().split(' ')))
	infected = list(map(int, input().split(' ')))
	infected.sort(key=lambda x: -x)
	ranges = []
	for i in range(1, m + 1):
		if i == m:
			ranges.append(infected[m - 1] + n - infected[0] - 1)
		else:
			ranges.append(infected[i - 1] - infected[i] - 1)
	ranges.sort(key=lambda x: -x)
	protect = 0
	count = 0
	for i in range(len(ranges)):
		current = ranges[i]
		if current - 2 * count > 0:
			temp = max(1, current - 2 * count - 1)
			protect += temp
		count += 2
	print(n - protect)
	t -= 1


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	res = []
	a.sort()
	for i in range(1, m):
		res.append(a[i] - a[i - 1] - 1)
	res.append(n - a[-1] + a[0] - 1)
	res.sort(reverse=True)
	k = 0
	for i in range(len(res)):
		res[i] -= k
		if res[i] == 1:
			k += 2
		else:
			k += 4
			res[i] -= 1
		res[i] = max(0, res[i])
	print(n - sum(res))


for _ in range(int(input())):
	(n, m) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	di = []
	a.sort()
	for i in range(1, m):
		di.append([a[i] - a[i - 1] - 1, 0])
	if n > 1:
		di.append([n - a[-1] + a[0] - 1, 0])
	di.sort()
	di.reverse()
	ans = 0
	c = 0
	if 4545555 == 'fhrgyughugtrhghr':
		print('Tanmay')
	aa = 0
	while di:
		if di[0][0] - c + aa > 0 and di[0][1] < 2:
			di[0][1] += 1
			if aa == 0:
				aa = 1
			else:
				aa = 0
			c += 2
			if di[0][1] == 2:
				ans += di[0][0] - c + 2
				del di[0]
			else:
				ans += 1
		else:
			break
	for i in di:
		ans += max(0, i[0] - c + aa)
	print(n - ans)


tests = int(input())

def get_pair_potential(a, b, n_houses):
	return (b - a) % n_houses - 1
for i in range(tests):
	(houses, infected) = map(int, input().split())
	infected_ids = sorted(list(map(int, input().split())))
	if infected == houses:
		print(infected)
		continue
	elif len(infected_ids) == 1:
		if houses == 2:
			print(1)
		elif houses > 2:
			print(2)
		continue
	pairs = []
	for (first, last) in zip(infected_ids, infected_ids[1:] + infected_ids[:1]):
		p_size = get_pair_potential(first, last, houses)
		pairs.append([p_size, [first, last]])
	pairs.sort(reverse=True)
	saved_houses = 0
	steps = 0
	for pair in pairs:
		(p_size, boundaries) = pair
		(first, last) = boundaries
		remaining_size = p_size - 2 * steps
		if remaining_size <= 0:
			break
		elif remaining_size <= 2:
			saved_houses += 1
			steps += 1
			continue
		else:
			saved_houses += remaining_size - 1
			steps += 2
			continue
	print(houses - saved_houses)


import heapq

class Node:

	def __init__(self, length):
		self.length = length

	def __lt__(self, other):
		return self.length > other.length

	def __repr__(self):
		return str(self.length)
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	infected = list(map(int, input().split()))
	if m == 1:
		if n <= 2:
			print(1)
		else:
			print(2)
		continue
	infected.sort()
	seq = []
	for i in range(len(infected) - 1):
		heapq.heappush(seq, Node(infected[i + 1] - infected[i] - 1))
	if len(infected) > 1:
		heapq.heappush(seq, Node(n - (infected[-1] - infected[0] + 1)))
	passed = 0
	protected = 0
	while seq:
		node = heapq.heappop(seq)
		if node.length - 2 * passed > 0:
			protected += max(1, node.length - 2 * passed - 1)
			passed += 2
	print(n - protected)