There is an infinite line of people, with person numbered (i+1) standing on the right of person numbered i. Chef can do 2 types of operations to this line of people:

Type 1: Give a ball to the person number 1.  
If there exists a person with two balls, they drop one ball and give the other ball to the person on their right, and this repeats until everyone has at most 1 ball.
Type 2: Everyone gives their ball to the person on their left simultaneously. Since there is no one to the left of person 1, they would drop their original ball if they have one.

Chef gives a total of N instructions, out of which K instructions are of type 2.  
Each instruction is numbered from 1 to N. The indices of instructions of type 2 are given by the array A_{1}, A_{2}, \dots, A_{K}. The rest operations are of type 1.

Find the number of balls that have been dropped by the end of all the instructions.

------ Input Format ------ 

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of multiple lines of input.
- The first line of each test case contains two space-separated integers N and K — the total number of operations and number of operations of type 2.
- The next line contains the array K space-separated integers A_{1}, A_{2}, \dots, A_{K} - the indices of instructions of type 2.

------ Output Format ------ 

For each test case, output on a new line the number of balls that have been dropped by the end of all the instructions.

------ Constraints ------ 

$1 ≤ T ≤ 100$
$1 ≤ N ≤ 10^{9}$
$1 ≤ K ≤ 10^{5}$
$1 ≤ A_{i} ≤ N$ for each $1 ≤ i ≤ M$
$A_{1} < A_{2} < \cdots < A_{K}$
- The sum of $K$ over all test cases won't exceed $10^{5}$.

----- Sample Input 1 ------ 
3
5 2
3 4
1 1
1
1000000000 5
271832455 357062697 396505195 580082912 736850926

----- Sample Output 1 ------ 
2
0
999999980

----- explanation 1 ------ 
Test case $1$: The operations are performed as follows:
- Type $1$: Only person $1$ has a ball. Till now, $0$ balls dropped.
- Type $1$: Person $1$ has $2$ balls. So he drops $1$ ball and passes $1$ to its right. Now, only person $2$ has a ball. Till now, $1$ ball dropped.
- Type $2$: Person $2$ passes the ball to its left. Now, only person $1$ has a ball. Till now, $1$ ball dropped.
- Type $2$: Person $1$ drops the ball. Till now, $2$ balls dropped.
- Type $1$: Only person $1$ has a ball. Till now, $2$ balls dropped.

In total, $2$ balls are dropped.

Test case $2$: Only one operation occurs which is of type $2$, so no balls are dropped.

Source: codechef | Difficulty: VERY_HARD
Tags: Bit manipulation

Mathematics


Solutions:
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	lst = list(map(int, input().split()))
	total_balls = 0
	for i in range(len(lst)):
		if i != 0:
			total_balls += lst[i] - lst[i - 1] - 1
		else:
			total_balls += lst[i] - 1
		total_balls = total_balls >> 1
		if i == len(lst) - 1:
			total_balls += n - lst[-1]
	minus = 0
	for i in range(30):
		if total_balls >> i & 1 == 1:
			minus += 1
	print(n - k - minus)


for i in range(int(input())):
	a = list(map(int, input().strip().split()))
	b = list(map(int, input().strip().split()))
	b.sort()
	ans = 0
	n = '{0:b}'.format(b[0] - 1)
	k = b[0] - 1
	o = 0
	for i in range(len(n)):
		if n[i] == '1':
			o += 1
	k -= o
	if n[-1] == '1':
		k += 1
	n = n[0:len(n) - 1]
	for i in range(1, a[1]):
		if b[i] - b[i - 1] - 1 > 0:
			o = 0
			for j in range(len(n)):
				if n[j] == '1':
					o += 1
			k += o
			o = 0
			if n == '':
				n = 0
			else:
				n = int(n, 2)
			n += b[i] - b[i - 1] - 1
			n = '{0:b}'.format(n)
			for j in range(len(n)):
				if n[j] == '1':
					o += 1
			k -= o
			k += b[i] - b[i - 1] - 1
		if n[-1] == '1':
			k += 1
		n = n[0:len(n) - 1]
	if a[0] - b[-1] > 0:
		o = 0
		for j in range(len(n)):
			if n[j] == '1':
				o += 1
		k += o
		o = 0
		if n == '':
			n = 0
		else:
			n = int(n, 2)
		n += a[0] - b[-1]
		n = '{0:b}'.format(n)
		for i in range(len(n)):
			if n[i] == '1':
				o += 1
		k -= o
		k += a[0] - b[-1]
	print(k)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	num = prv = 0
	for x in a:
		num += x - prv - 1
		num //= 2
		prv = x
	num += n - prv
	print(n - k - bin(num)[2:].count('1'))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	prev = 0
	c = 1
	for i in arr:
		a = i + prev - c
		prev = a // 2
		c = i + 1
	prev += n - c + 1
	b = bin(prev)
	c = b.count('1')
	a = n - k - c
	print(a)


try:
	for _ in range(int(input())):
		(n, k) = map(int, input().split())
		a = [0] + sorted(map(int, input().split()))
		(c, v) = (0, 0)
		for (i, curr) in enumerate(a[1:], start=1):
			v += curr - 1 - a[i - 1]
			v //= 2
		v += n - a[-1]
		print(n - k - format(v, 'b').count('1'))
except Exception as e:
	raise e


t = int(input())
for _ in range(t):
	s = input().split()
	(n, k) = map(int, s)
	s = input().split()
	arr = list(map(int, s))
	arr.sort()
	curNum = arr[0] - 1
	for i in range(k - 1):
		curNum = curNum >> 1
		curNum += arr[i + 1] - arr[i] - 1
	curNum = curNum >> 1
	curNum += n - arr[-1]
	print(n - k - bin(curNum).count('1'))


def cal(a, b):
	dp = 0
	for i in range(35):
		dp += int(a >> i & 1) * (2 ** i - 1) - int(b >> i & 1) * (2 ** i - 1)
	return dp
import math
for i in range(int(input())):
	(n, k) = [int(i) for i in input().split()]
	a = [int(i) for i in input().split()]
	a = [0] + a
	prv = 0
	nm = 0
	dr = 0
	for i in range(1, k + 1):
		inc = a[i] - a[i - 1] - 1
		dr += cal(nm + inc, nm)
		nm += inc
		dr += nm % 2
		nm //= 2
	inc = n - a[i]
	dr += cal(nm + inc, nm)
	print(dr)


def cal(a, b):
	d = 0
	for i in range(35):
		d += int(a >> i & 1) * (2 ** i - 1) - int(b >> i & 1) * (2 ** i - 1)
	return d
import math
for _ in range(int(input())):
	(n, k) = [int(i) for i in input().split()]
	a = [int(i) for i in input().split()]
	a = [0] + a
	pr = 0
	nm = 0
	dr = 0
	for i in range(1, k + 1):
		inc = a[i] - a[i - 1] - 1
		dr += cal(nm + inc, nm)
		nm += inc
		dr += nm % 2
		nm //= 2
	inc = n - a[i]
	dr += cal(nm + inc, nm)
	print(dr)


def calc(a, b):
	dp = 0
	for i in range(35):
		dp += int(a >> i & 1) * (2 ** i - 1) - int(b >> i & 1) * (2 ** i - 1)
	return dp
import math
for _ in range(int(input())):
	(n, k) = [int(i) for i in input().split()]
	a = [int(i) for i in input().split()]
	a = [0] + a
	prv = 0
	nm = 0
	drp = 0
	for i in range(1, k + 1):
		inc = a[i] - a[i - 1] - 1
		drp += calc(nm + inc, nm)
		nm += inc
		drp += nm % 2
		nm //= 2
	inc = n - a[i]
	drp += calc(nm + inc, nm)
	print(drp)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	a = [*map(int, input().split())]
	num = prv = 0
	for x in a:
		num += x - prv - 1
		num //= 2
		prv = x
	num += n - prv
	print(n - k - bin(num).count('1'))


t = int(input())
while t:
	(x, y) = map(int, input().split(' '))
	l = list(map(int, input().split(' ')))
	c = 0
	a = l[0] - 1
	for i in range(y):
		if i >= 1:
			a += l[i] - l[i - 1] - 1
		a >>= 1
	a += x - l[-1]
	b = x - y - bin(a).count('1')
	print(b)
	t -= 1


from sys import stdin
input = stdin.readline
inp = lambda : list(map(int, input().split()))

def answer():
	(ans, prev, pv) = (0, 0, 0)
	for i in range(k + 1):
		count = prev + (a[i] - pv - 1)
		for bit in range(30):
			if count >> bit & 1:
				if bit:
					ans += (1 << bit) - 1
		if a[i] == n + 1:
			break
		cur = prev + (a[i] - pv - 1)
		if cur & 1:
			ans += 1
		cur >>= 1
		for bit in range(30):
			if cur >> bit & 1:
				if bit:
					ans -= (1 << bit) - 1
		prev = cur
		pv = a[i]
	return ans
for T in range(int(input())):
	(n, k) = inp()
	a = inp()
	a.append(n + 1)
	print(answer())


import sys

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

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

def oper(n):
	val = 0
	x = 2
	cur = n // x
	while cur >= 1:
		val += cur
		x = x * 2
		cur = n // x
	return val
t = int(sys.stdin.readline())
for _ in range(t):
	(n, k) = get_ints()
	a = get_arr()
	a.append(n + 1)
	ans = oper(a[0] - 1)
	val = a[0] - 1
	for i in range(k):
		if val % 2 != 0:
			ans += 1
		val = val >> 1
		if val < 0:
			val = 0
		ans -= oper(val)
		val2 = a[i + 1] - a[i] - 1
		val += val2
		ans += oper(val)
	print(ans)


for test in range(int(input())):
	(n, k) = map(int, input().split())
	a = [int(ai) for ai in input().split()]
	line = 0
	balls = 0
	runs = [a[0] - 1]
	for i in range(k - 1):
		runs.append(a[i + 1] - a[i] - 1)
	runs.append(n - a[k - 1])
	prevcount = 0
	for i in range(k):
		line += runs[i]
		newcount = bin(line).count('1')
		balls += runs[i] + prevcount - newcount
		prevcount = newcount
		l2 = line % 2
		balls += l2
		prevcount -= l2
		line >>= 1
	line += runs[k]
	balls += runs[k] + prevcount - bin(line).count('1')
	print(balls)


from collections import defaultdict

def get_set_bits(x):
	cnt = 0
	while x > 0:
		if x % 2 == 1:
			cnt += 1
		x //= 2
	return cnt

def solve():
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	balls_given = n - k
	ans = 0
	steps = [0] + sorted(arr)
	for i in range(1, len(steps)):
		ans += steps[i] - steps[i - 1] - 1
		ans //= 2
	ans += n - steps[-1]
	return balls_given - get_set_bits(ans)
for _ in range(int(input())):
	print(solve())


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

def li():
	return list(mi())

def si():
	return str(input())

def ni():
	return int(input())

def f(n):
	ans = bin(n)
	return ans.count('1')
for t in range(int(input())):
	(n, k) = mi()
	a = li()
	a.append(n + 1)
	ans = 0
	pre = 0
	count = 0
	for i in a:
		ans += i - pre - 1
		if i == n + 1:
			continue
		count += ans % 2
		ans //= 2
		pre = int(i)
	print(n - k - f(ans))


T = int(input())
for i in range(T):
	[N, K] = list(map(int, input().split()))
	A = list(map(int, input().split()))
	b = A[0] - 1
	for i in range(K):
		if i > 0:
			b += A[i] - A[i - 1] - 1
		s = bin(b).split('b')[1]
		b = int(s[:-1].zfill(1), 2)
	b += N - A[-1]
	r = 0
	for i in bin(b).split('b')[1]:
		r += int(i)
	print(N - K - r)


import random
import math
from collections import defaultdict, Counter, deque, OrderedDict
from functools import lru_cache
import bisect
import heapq
import sys
input = lambda : sys.stdin.readline().strip()

class SegmentTree:

	def __init__(self, nums):
		self._size = len(nums)
		self._tree = [0] * (4 * self._size)
		self.build(nums)

	def build(self, a, v=1, lo=0, hi=None):
		if hi is None:
			hi = self._size - 1
		if lo == hi:
			self._tree[v] = a[lo]
		else:
			mi = (lo + hi) // 2
			self.build(a, 2 * v, lo, mi)
			self.build(a, 2 * v + 1, mi + 1, hi)
			self._tree[v] = self._tree[2 * v] + self._tree[2 * v + 1]

	def update(self, pos, val, v=1, lo=0, hi=None):
		if hi is None:
			hi = self._size - 1
		if lo == hi:
			self._tree[v] = val
		else:
			mi = (lo + hi) // 2
			if pos <= mi:
				self.update(pos, val, 2 * v, lo, mi)
			else:
				self.update(pos, val, 2 * v + 1, mi + 1, hi)
			self._tree[v] = self._tree[2 * v] + self._tree[2 * v + 1]

	def query(self, l, h, v=1, lo=0, hi=None):
		if hi is None:
			hi = self._size - 1
		if l > h:
			return 0
		elif l == lo and h == hi:
			return self._tree[v]
		else:
			mi = (lo + hi) // 2
			return self.query(l, min(mi, h), 2 * v, lo, mi) + self.query(max(mi + 1, l), h, 2 * v + 1, mi + 1, hi)

class UnionFind:

	def __init__(self, n):
		self.n = n
		self.parents = list(range(n))

	def find(self, x):
		if self.parents[x] == x:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x != y:
			self.parents[x] = y
dire = [0, 1, 0, -1, 0]

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

def case(t):
	print('Case #{}:'.format(t), end=' ')
RANDOM = random.randrange(2 ** 62)

def Wrapper(x):
	return x ^ RANDOM

def solve():
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	ans = 0
	last = 0
	actual = 0
	for i in a:
		added = i - 1 - last
		oldcount = format(actual, 'b').count('1')
		actual += added
		ans += added + oldcount - format(actual, 'b').count('1')
		last = i
		if actual % 2 == 1:
			ans += 1
		actual = actual >> 1
	if a[-1] != n:
		i = n
		added = i - last
		oldcount = format(actual, 'b').count('1')
		actual += added
		ans += added + oldcount - format(actual, 'b').count('1')
	print(ans)
for t in range(int(input())):
	solve()


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	k_pos = list(map(int, input().split()))
	num = k_pos[0] - 1
	for i in range(1, k):
		num = num >> 1
		num += k_pos[i] - k_pos[i - 1] - 1
		if i == k - 1:
			num = num >> 1
	if k == 1:
		num = num >> 1
	num += n - k_pos[-1]
	num = bin(num)
	ones = num.count('1')
	print(n - k - ones)


def bitsum(n):
	return sum(map(int, f'{n:b}'))

def dropstill(n):
	return n - bitsum(n)

def getdrops(nombre, newnombre):
	return dropstill(newnombre) - dropstill(nombre)
T = int(input())
for i in range(T):
	(N, K) = map(int, input().split())
	typeoneses = list(map(int, input().split()))
	typeoneses.append(N + 1)
	for j in range(K, 0, -1):
		typeoneses[j] -= typeoneses[j - 1] + 1
	typeoneses[0] -= 1
	nombre = 0
	drops = 0
	for j in range(K):
		typeones = typeoneses[j]
		newnombre = nombre + typeones
		drops += getdrops(nombre, newnombre)
		nombre = newnombre
		drops += nombre % 2
		nombre >>= 1
	drops += getdrops(nombre, nombre + typeoneses[-1])
	print(drops)


import sys
from collections import defaultdict
from math import log2
input = sys.stdin.readline
I = lambda : map(int, input().split())
ii = lambda : int(input())
mod = 10 ** 9 + 7

def jaadu(n):
	if n <= 1:
		return 0
	x = int(log2(n))
	f = 1 << x
	ans = 0
	for i in range(x):
		ans = ans * 2 + 1
	return ans + jaadu(n - f)
for _ in range(ii()):
	(n, k) = I()
	a = [*I()]
	lambu = 0
	ans = 0
	chotu = 0
	for i in range(k):
		temp = lambu
		lambu += a[i] - chotu - 1
		chotu = a[i]
		ans += jaadu(lambu) - jaadu(temp)
		if lambu & 1:
			ans += 1
		lambu >>= 1
	temp = lambu
	lambu += n - chotu
	ans += jaadu(lambu) - jaadu(temp)
	print(ans)


import sys
from math import sqrt, gcd, factorial, ceil, floor, pi
from collections import deque, Counter, OrderedDict
from heapq import heapify, heappush, heappop
input = lambda : sys.stdin.readline()
I = lambda : int(input())
S = lambda : input().strip()
M = lambda : map(int, input().strip().split())
L = lambda : list(map(int, input().strip().split()))
mod = 10 ** 9 + 7

def solver(val):
	y = 0
	for i in range(32):
		y += val // 2 ** (i + 1)
	return y
for _ in range(I()):
	(n, k) = M()
	a = [0] + L()
	x = 0
	ans = 0
	for i in range(1, k + 1):
		t = x + a[i] - a[i - 1] - 1
		ans += solver(t) - solver(x) + t % 2
		if bin(t)[2:-1]:
			x = int(bin(t)[2:-1], 2)
		else:
			x = 0
	ans += solver(n - a[-1] + x) - solver(x)
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	s = 0
	ans = 0
	for i in range(k):
		if i == 0:
			s += a[i] - 1
		else:
			s += a[i] - a[i - 1] - 1
		s >>= 1
	s += n - a[-1]
	balls = n - k
	c = 0
	while s:
		if s & 1:
			c += 1
		s >>= 1
	ans += balls - c
	print(ans)


def f(x):
	ans = 0
	p = 0
	while x != 0:
		if x & 1 == 1:
			ans += pow(2, p) - 1
		x >>= 1
		p += 1
	return ans
for case in range(int(input())):
	(n, k) = (int(i) for i in input().split())
	d = [int(i) for i in input().split()]
	m = 0
	p = 0
	ans = 0
	for i in d:
		ans += f(m + i - 1 - p) - f(m)
		if m + i - 1 - p & 1 == 1:
			ans += 1
		m = m + i - 1 - p >> 1
		p = i
	ans += f(m + n - p) - f(m)
	print(ans)


def f():
	(n, k) = map(int, input().split())
	v = list(map(int, input().split()))
	last = 0
	ans = 0
	for i in range(k):
		temp = v[i]
		diff = temp - last
		ans += diff
		ans = ans // 2
		last = v[i]
	ans += n - last - 1
	st = 0
	while ans > 0:
		pop = ans % 2
		if pop:
			st += 1
		ans //= 2
	print(n - k - st)
t = int(input())
while t:
	f()
	t -= 1


from itertools import count
import sys
sys.setrecursionlimit(25000)
cin = sys.stdin
read = cin.readline
cout = sys.stdout
write = cout.write
ir = lambda : int(read())
rir = lambda : range(int(read()))
mir = lambda : map(int, read().split())
lmir = lambda : list(map(int, read().split()))

def carry(n):
	return 0 if n <= 0 else carry(n >> 1) + (n >> 1)

def range_carry(l, r):
	return carry(r) - carry(l)
for _ in rir():
	(n, k) = mir()
	two = lmir()
	res = x = 0
	last = 0
	for i in two:
		adds = i - last - 1
		res += range_carry(x, x + adds)
		x += adds
		res += x & 1
		x >>= 1
		last = i
	res += range_carry(x, x + n - i)
	print(res)