You are given a multiset $S$ initially consisting of $n$ distinct non-negative integers. A multiset is a set, that can contain some elements multiple times.

You will perform the following operation $k$ times:

Add the element $\lceil\frac{a+b}{2}\rceil$ (rounded up) into $S$, where $a = \operatorname{mex}(S)$ and $b = \max(S)$. If this number is already in the set, it is added again.

Here $\operatorname{max}$ of a multiset denotes the maximum integer in the multiset, and $\operatorname{mex}$ of a multiset denotes the smallest non-negative integer that is not present in the multiset. For example:

$\operatorname{mex}(\{1,4,0,2\})=3$;

$\operatorname{mex}(\{2,5,1\})=0$.

Your task is to calculate the number of distinct elements in $S$ after $k$ operations will be done.


-----Input-----

The input consists of multiple test cases. The first line contains a single integer $t$ ($1\le t\le 100$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $n$, $k$ ($1\le n\le 10^5$, $0\le k\le 10^9$) — the initial size of the multiset $S$ and how many operations you need to perform.

The second line of each test case contains $n$ distinct integers $a_1,a_2,\dots,a_n$ ($0\le a_i\le 10^9$) — the numbers in the initial multiset.

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


-----Output-----

For each test case, print the number of distinct elements in $S$ after $k$ operations will be done.


-----Examples-----

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


-----Note-----

In the first test case, $S={0,1,3,4\}$, $a=\operatorname{mex}(S)=2$, $b=\max(S)=4$, $\lceil\frac{a+b}{2}\rceil=3$. So $3$ is added into $S$, and $S$ becomes $\{0,1,3,3,4\}$. The answer is $4$.

In the second test case, $S={0,1,4\}$, $a=\operatorname{mex}(S)=2$, $b=\max(S)=4$, $\lceil\frac{a+b}{2}\rceil=3$. So $3$ is added into $S$, and $S$ becomes $\{0,1,3,4\}$. The answer is $4$.

Source: codeforces | Difficulty: EASY
Tags: Mathematics


Solutions:
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	m = a[-1]
	if a[0] != 0:
		if (m + 1) // 2 in a:
			print(n)
		elif k == 0:
			print(n)
		else:
			print(n + 1)
	else:
		mex = 0
		for i in range(n):
			if a[i] != i:
				mex = i
				break
		if mex == 0 or mex == m - 1:
			print(n + k)
		elif (m + mex + 1) // 2 in a:
			print(n)
		elif k == 0:
			print(n)
		else:
			print(n + 1)


import math
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	ar = list(map(int, input().split()))
	al = True
	ar = set(ar)
	ar = list(ar)
	n = len(ar)
	for x in range(n):
		if ar[x] != x:
			mex = x
			al = False
			break
	if al:
		print(n + k)
	elif math.ceil((mex + ar[n - 1]) / 2) in ar or k == 0:
		print(n)
	else:
		print(n + 1)


T = int(input())
for _ in range(T):
	(N, K) = map(int, input().split())
	A = list(map(int, input().split()))
	if K == 0:
		print(N)
		continue
	ma = max(A)
	me = 0
	for a in sorted(A):
		if a == me:
			me += 1
	if ma < me:
		print(N + K)
		continue
	st = set(A)
	for i in range(K):
		add = (ma + me + 1) // 2
		if add in st:
			break
		st.add(add)
	print(len(st))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	l = sorted(l)
	mex = -1
	for i in range(len(l)):
		if l[i] != i:
			mex = i
			break
	if mex == -1:
		mex = n
	mx = max(l)
	x = mx + mex
	if x % 2 == 0:
		x = x // 2
	else:
		x = x // 2 + 1
	if x == mx:
		print(len(l))
	elif x == mex:
		print(k + len(l))
	else:
		y = len(l)
		if x not in l and k > 0:
			y += 1
		print(y)


from collections import defaultdict
import math
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	d = defaultdict(lambda : 0)
	for i in l:
		d[i] += 1
	l.sort()
	mex = -1
	for i in range(n - 1):
		if l[i + 1] - l[i] > 1:
			mex = l[i] + 1
			break
	if mex == -1 and 0 in d:
		print(len(d) + k)
	else:
		if mex == -1:
			mex = 0
		if k == 0:
			print(len(d))
		elif math.ceil((l[-1] + mex) / 2) in d:
			print(len(d))
		else:
			print(len(d) + 1)


import math

def solve():
	(n, k) = map(int, input().split())
	a = set(map(int, input().split()))
	inside = [False] * (n + 1)
	maximal = max(a)
	for num in a:
		if num <= n:
			inside[num] = True
	mex = inside.index(False)
	if k == 0:
		return len(a)
	if mex == maximal + 1:
		return len(a) + k
	if math.ceil((mex + maximal) / 2) > n or not inside[math.ceil((mex + maximal) / 2)]:
		return len(a) + 1
	return len(a)
t = int(input())
while t > 0:
	t -= 1
	print(solve())


from math import ceil
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	li = sorted(map(int, input().split()))
	mx = li[-1]
	if k == 0 or mx == n - 1:
		print(n + k)
		continue
	mex = 0
	i = 0
	while mex == li[i]:
		i += 1
		mex += 1
	check = ceil((mx + mex) / 2)
	if check in li:
		print(n)
	else:
		print(n + 1)


from math import *

def solve():
	(n, k) = map(int, input().split())
	l = set(map(int, input().split()))
	if k == 0:
		print(n)
		return
	m = max(l)
	val = -1
	for i in range(n):
		if i not in l:
			val = i
			break
	else:
		print(n + k)
		return
	if ceil((val + m) / 2) in l:
		print(n)
		return
	print(n + 1)
t = int(input())
for _ in range(t):
	solve()


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	nums = set(map(int, input().split()))
	maX = max(nums)
	mex = 0
	while mex in nums:
		mex += 1
	if mex > maX or k == 0:
		print(n + k)
	else:
		print(n if (mex + maX + 1) // 2 in nums else n + 1)


R = lambda : map(int, input().split())
(t,) = R()
while t:
	t -= 1
	(n, k) = R()
	a = {*R()}
	i = 0
	while {i} & a:
		i += 1
	print(n + (k > 0) * (k, i + max(a) + 1 >> 1 not in a)[i < n])


import math
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = [*set(map(int, input().split()))]
	a.sort()
	mx = a[-1]
	mex = 0
	l = len(a)
	if k == 0:
		print(l)
	else:
		for i in range(l):
			if mex == a[i]:
				mex += 1
			elif mex < a[i]:
				break
		if mex > mx:
			print(l + k)
		elif math.ceil((mex + mx) / 2) in a:
			print(l)
		else:
			print(l + 1)


rn = lambda : int(input())
rns = lambda : map(int, input().split())
rl = lambda : list(map(int, input().split()))
rs = lambda : input()
YN = lambda x: print('YES') if x else print('NO')
mod = 10 ** 9 + 7
from math import ceil
for _ in range(rn()):
	(n, k) = rns()
	s = rl()
	m = max(s)
	h = set(s)
	if k == 0:
		print(len(h))
	else:
		for i in range(10 ** 9 + 1):
			if i not in h:
				if i > m:
					print(len(h) + k)
				elif ceil((i + m) / 2) not in h:
					print(len(h) + 1)
				else:
					print(len(h))
				break


t = int(input())
while t > 0:
	(n, k) = map(int, input().split())
	l = set(map(int, input().split()))
	m1 = max(l)
	m2 = 0
	for i in range(m1 + 2):
		if i not in l:
			m2 = i
			break
	if m2 == m1 + 1:
		print(len(l) + k)
	else:
		if k > 0:
			l.add((m1 + m2 + 1) // 2)
		print(len(l))
	t -= 1


from sys import stdin
input = stdin.readline
from heapq import heapify, heappush, heappop, heappushpop
from collections import defaultdict as dd, deque as dq, Counter as C
from math import factorial as f, ceil, gcd, sqrt, log
from bisect import bisect_left as bl, bisect_right as br
from itertools import combinations as c, permutations as p
from math import factorial as f, ceil, gcd, sqrt, log
mi = lambda : map(int, input().split())
ii = lambda : int(input())
li = lambda : list(map(int, input().split()))
mati = lambda r: [li() for _ in range(r)]
lcm = lambda a, b: a * b // gcd(a, b)

def solve():
	(n, k) = mi()
	arr = li()
	arr.sort()
	mex = -1
	for x in range(n):
		if arr[x] != x:
			mex = x
			break
	ans = len(list(set(arr)))
	if mex == -1:
		mex = arr[-1] + 1
		ans += k
	elif ceil((mex + max(arr)) / 2) not in arr and k > 0:
		ans += 1
	print(ans)
for _ in range(ii()):
	solve()


import math
t = int(input())
for _ in range(t):
	(n, k) = list(map(int, input().split()))
	s = set(list(map(int, input().split())))
	arr = list(s)
	arr.sort()
	m = len(arr)
	maxi = max(arr)
	mex = m
	for i in range(m):
		if arr[i] != i:
			mex = i
			break
	if k == 0:
		print(m)
	else:
		r = int(math.ceil((mex + maxi) / 2))
		if r < mex:
			print(m)
		elif r > mex:
			if r in s:
				print(m)
			else:
				print(m + 1)
		elif r == mex:
			print(m + k)


def mex(arr):
	n = len(arr)
	v = set(arr)
	for i in range(0, n):
		if i not in v:
			return i
	return n + 1
from math import ceil
for _ in range(int(input())):
	(n, k) = map(int, input().split(' '))
	arr = [int(num) for num in input().split(' ')]
	if k == 0:
		ans = n
	else:
		a = mex(arr)
		b = max(arr)
		if a > b:
			ans = n + k
		else:
			f = ceil((a + b) / 2)
			if f not in arr:
				ans = n + 1
			else:
				ans = n
	print(ans)


import math
import bisect
tests = int(input().strip())
while tests:
	tests -= 1
	(n, k) = map(int, input().strip().split())
	array = list(set(map(int, input().strip().split())))
	n = len(array)
	array.sort()
	max_member = array[-1]
	mex = n if max_member == n - 1 else None
	if mex is None:
		for i in range(0, n):
			if array[i] != i:
				mex = i
				break
	if mex == n:
		print(n + k)
	else:
		added = math.ceil((mex + max_member) / 2)
		pos = bisect.bisect_left(array, added)
		if array[pos] == added:
			print(n)
		else:
			print(n + min(1, k))


from math import *
t = int(input())

def mex(arr, n):
	arr.sort()
	for i in range(n):
		if i != arr[i]:
			return i
	return arr[-1] + 1
for _ in range(t):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr.sort()
	a = mex(arr, n)
	b = max(arr)
	if k == 0:
		print(n)
	elif a > b:
		print(n + k)
	elif ceil((a + b) / 2) not in arr:
		print(n + 1)
	elif ceil((a + b) / 2) in arr:
		print(n)


for t in range(int(input())):
	(n, k) = map(int, input().split())
	lis = list(map(int, input().split()))
	s = set(lis)
	Max = max(lis)
	min = 0
	for i in range(Max + 2):
		if i not in s:
			min = i
			break
	if min == Max + 1:
		print(n + k)
		continue
	if k > 0:
		s.add((Max + min + 1) // 2)
	print(len(s))


import sys
input = sys.stdin.readline
from math import ceil
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	w = sorted(map(int, input().split()))
	for i in range(n):
		if w[i] != i:
			if ceil((i + max(w)) / 2) in w:
				print(n)
			else:
				print(min(k + n, n + 1))
			break
	else:
		print(n + k)


T = int(input())
for x in range(T):
	b = [int(y) for y in input().split()]
	n = b[0]
	k = b[1]
	a = [int(z) for z in input().split()]
	d = 0
	f = set(a)
	c = len(f)
	m = max(f)
	if k == 0:
		print(c)
	else:
		for p in range(m + 2):
			if p not in f:
				d = p
				break
		if d == m + 1:
			print(c + k)
		else:
			e = 0
			if (m + d) % 2 == 0:
				e = int((m + d) / 2)
			else:
				e = int((m + d) / 2) + 1
			if e in f:
				print(c)
			else:
				print(c + 1)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	arr = [int(j) for j in input().split()]
	arr = list(set(arr))
	arr.sort()
	if k == 0:
		print(len(arr))
		continue
	if arr[0] != 0:
		mex = 0
	else:
		flag = 0
		for i in range(1, n):
			if arr[i] != arr[i - 1] + 1:
				flag = 1
				mex = arr[i - 1] + 1
		if flag == 0:
			mex = arr[-1] + 1
	ma = arr[-1]
	if mex == ma + 1:
		print(len(arr) + k)
	else:
		new = (mex + ma) // 2
		if (mex + ma) % 2 != 0:
			new += 1
		if new in arr:
			print(len(arr))
		else:
			print(len(arr) + 1)


import sys, math
input = sys.stdin.readline
numOfTests = int(input())

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

def getMex(num, maximum, start):
	for i in range(start, maximum):
		if i not in num:
			return i
	return maximum + 1
for _ in range(numOfTests):
	(n, k) = invr()
	nums = list(set(invr()))
	numsLength = len(nums)
	if k == 0:
		print(numsLength)
		continue
	writtenFlag = False
	maxim = max(nums)
	if maxim == numsLength - 1:
		print(numsLength + k)
		continue
	mex = getMex(nums, maxim, 0)
	if mex == maxim + 1:
		print(numsLength + k)
		continue
	for i in range(k):
		toAdd = math.ceil((maxim + mex) / 2)
		if toAdd in nums:
			break
		nums.append(toAdd)
		numsLength += 1
		if toAdd <= maxim and toAdd != mex:
			break
		if toAdd > maxim:
			maxim = toAdd
		if toAdd == mex or mex == maxim + 1:
			print(numsLength + k - i - 1)
			writtenFlag = True
			break
	if not writtenFlag:
		print(numsLength)


def solve(A, n, k):
	setA = set(A)
	ls = len(setA)
	if k == 0:
		return ls
	mexVal = ls
	for i in range(ls):
		if i not in setA:
			mexVal = i
			break
	if mexVal < ls:
		result = ls
		if (mexVal + max(setA) + 1) // 2 not in setA:
			result += 1
	else:
		result = ls + k
	return result
t = int(input())
for tc in range(t):
	(n, k) = map(int, input().split())
	A = list(map(int, input().split()))
	result = solve(A, n, k)
	print(result)


import math

def mex(arr, n):
	for i in range(n):
		if arr[i] != i:
			return i
	return i + 1

def answer(n, k, arr):
	if k == 0:
		return n
	arr.sort()
	m = mex(arr, n)
	M = arr[n - 1]
	if m == M - 1:
		return n
	elif m == M + 1:
		return n + k
	else:
		number = math.ceil((m + M) / 2)
		if number in arr:
			return n
		else:
			return n + 1
t = int(input())
for i in range(t):
	[n, k] = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	print(answer(n, k, arr))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = list(map(int, input().split()))
	s.sort()
	a = max(s)
	flag = 0
	s = set(s)
	for i in s:
		if i == flag:
			flag += 1
		else:
			break
	if k == 0:
		ans = n
		print(ans)
	elif flag > a:
		ans = n + k
		print(ans)
	else:
		s.add((flag + a + 1) // 2)
		print(len(s))


from sys import stdin, stdout
from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import *
input = stdin.readline
from random import sample
t = int(input())
from collections import Counter, deque
from math import sqrt, ceil, log2, gcd

class DisjSet:

	def __init__(self, n):
		self.rank = [1] * n
		self.parent = [i for i in range(n)]

	def find(self, x):
		if self.parent[x] != x:
			self.parent[x] = self.find(self.parent[x])
		return self.parent[x]

	def union(self, x, y):
		xset = self.find(x)
		yset = self.find(y)
		if xset == yset:
			return
		if self.rank[xset] < self.rank[yset]:
			self.parent[xset] = yset
		elif self.rank[xset] > self.rank[yset]:
			self.parent[yset] = xset
		else:
			self.parent[yset] = xset
			self.rank[xset] = self.rank[xset] + 1

def f(arr, i, j, d, dist):
	if i == j:
		return
	nn = max(arr[i:j])
	for tl in range(i, j):
		if arr[tl] == nn:
			dist[tl] = d
			f(arr, i, tl, d + 1, dist)
			f(arr, tl + 1, j, d + 1, dist)

def ps(n):
	cp = 0
	while n % 2 == 0:
		n = n // 2
		cp += 1
	for ps in range(3, ceil(sqrt(n)) + 1, 2):
		while n % ps == 0:
			n = n // ps
			cp += 1
	if n != 1:
		return False
	return True

def find_gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def factorials(n, r):
	slr = n
	dpr = r
	qlr = 1
	qs = 1
	mod = 10 ** 9 + 7
	for ip in range(n - r + 1, n + 1):
		qlr = qlr * ip % mod
	for ij in range(1, r + 1):
		qs = qs * ij % mod
	ans = qlr * modInverse(qs) % mod
	return ans

def modInverse(b):
	qr = 10 ** 9 + 7
	return pow(b, qr - 2, qr)
tt = [xa ** 3 for xa in range(0, 10 ** 4 + 1)]
qq = set(tt)

def digits(k, rp):
	n = len(k)
	pq = k[::-1]
	jq = ''
	for ij in pq:
		if ij == '1':
			jq += '1'
		elif ij == '2':
			jq += '5'
		elif ij == '4' or ij == '7' or ij == '3' or (ij == '6') or (ij == '9'):
			jq += '-'
		elif ij == '5':
			jq += '2'
		elif ij == '8':
			jq += '8'
		elif ij == '0':
			jq += '0'
	if jq.find('-') != -1:
		return -1
	else:
		jl = int(jq)
		if jl >= rp:
			return -1
		else:
			return jq

def fr(a, b, h, m):
	kl = int(b)
	kl = (kl + 1) % m
	b = '0' * (2 - len(str(kl))) + str(kl)
	if b == '0' * 2:
		kj = (int(a) + 1) % h
		a = '0' * (2 - len(str(kj))) + str(kj)
	return [a, b]
for jj in range(t):
	(n, k) = [int(x) for x in input().strip().split()]
	arr = [int(x) for x in input().strip().split()]
	arr = sorted(arr)
	tr = set(arr)
	if k == 0:
		print(len(tr))
		continue
	sq = [i for i in range(10 ** 5)]
	ans = -1
	for ip in range(n):
		if ip not in tr:
			ans = ip
			break
		elif ip == n - 1:
			ans = n
	if ans == n:
		print(len(tr) + k)
	elif ceil((ans + arr[-1]) / 2) in tr:
		print(len(tr))
	else:
		print(len(tr) + 1)


def mex(a):
	i = 0
	while i in a:
		i += 1
	return i
from math import ceil
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	ar = set((int(j) for j in input().split()))
	a = mex(ar)
	b = max(ar)
	c = ceil((a + b) / 2)
	if a == n:
		print(n + k)
	elif k != 0:
		if c in ar:
			print(n)
		else:
			print(n + 1)
	else:
		print(n)


from bisect import bisect_left
from sys import stdin, gettrace
if gettrace():

	def inputi():
		return input()
else:

	def input():
		return next(stdin)[:-1]

	def inputi():
		return stdin.buffer.readline()

def solve():
	(n, k) = map(int, input().split())
	aa = [int(a) for a in input().split()]
	if k == 0:
		print(n)
		return
	aa.sort()

	def mexf(aa):
		if aa[0] != 0:
			return 0
		else:
			c = aa[0]
			for a in aa[1:]:
				if a != c + 1:
					return c + 1
				c += 1
			return c + 1
	mx = aa[-1]
	mex = mexf(aa)
	if mex > mx:
		print(n + k)
		return
	new = (mex + mx + 1) // 2
	p = bisect_left(aa, new)
	if aa[p] == new:
		print(n)
	else:
		print(n + 1)

def main():
	t = int(input())
	for _ in range(t):
		solve()
main()


t = int(input())
import math
for _ in range(t):
	(n, k) = map(int, input().split())
	s = list(map(int, input().split()))
	s = set(s)
	b = max(s)
	for i in range(b + 2):
		if i not in s:
			a = i
			break
	if a > b:
		print(len(s) + k)
	elif math.ceil((a + b) / 2) not in s:
		print(len(s) + min(1, k))
	else:
		print(len(s))


import math
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	a = set(map(int, input().split()))
	mex = 0
	while mex in a:
		mex = mex + 1
	if k == 0:
		print(n)
	elif mex != n:
		x = math.ceil((mex + max(a)) / 2)
		ans = n
		if x not in a:
			ans = ans + 1
		print(ans)
	elif mex == n:
		ans = n + k
		print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	st = set(map(int, input().split()))
	a = 0
	if k:
		while a in st:
			a += 1
		b = max(st)
		tmp = (a + b + 1) // 2
		if tmp != a:
			st.add(tmp)
			k = 0
	print(len(st) + k)


from bisect import *
from collections import *
from math import gcd, ceil, sqrt, floor, inf
from heapq import *
from itertools import *
from operator import add, mul, sub, xor, truediv, floordiv
from functools import *
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')

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 A(n):
	return [0] * n

def AI(n, x):
	return [x] * n

def A2(n, m):
	return [[0] * m for i in range(n)]

def G(n):
	return [[] for i in range(n)]

def GP(it):
	return [[ch, len(list(g))] for (ch, g) in groupby(it)]
from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc
mod = 10 ** 9 + 7
farr = [1]
ifa = []

def fact(x, mod=0):
	if mod:
		while x >= len(farr):
			farr.append(farr[-1] * len(farr) % mod)
	else:
		while x >= len(farr):
			farr.append(farr[-1] * len(farr))
	return farr[x]

def ifact(x, mod):
	global ifa
	fact(x, mod)
	ifa.append(pow(farr[-1], mod - 2, mod))
	for i in range(x, 0, -1):
		ifa.append(ifa[-1] * i % mod)
	ifa.reverse()

def per(i, j, mod=0):
	if i < j:
		return 0
	if not mod:
		return fact(i) // fact(i - j)
	return farr[i] * ifa[i - j] % mod

def com(i, j, mod=0):
	if i < j:
		return 0
	if not mod:
		return per(i, j) // fact(j)
	return per(i, j, mod) * ifa[j] % mod

def catalan(n):
	return com(2 * n, n) // (n + 1)

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

def floorsum(a, b, c, n):
	if a == 0:
		return b // c * (n + 1)
	if a >= c or b >= c:
		return floorsum(a % c, b % c, c, n) + b // c * (n + 1) + a // c * n * (n + 1) // 2
	m = (a * n + b) // c
	return n * m - floorsum(c, c - b - 1, a, m - 1)

def inverse(a, m):
	a %= m
	if a <= 1:
		return a
	return (1 - inverse(m, a) * m) // a % m

def lowbit(n):
	return n & -n

class BIT:

	def __init__(self, arr):
		self.arr = arr
		self.n = len(arr) - 1

	def update(self, x, v):
		while x <= self.n:
			self.arr[x] += v
			x += x & -x

	def query(self, x):
		ans = 0
		while x:
			ans += self.arr[x]
			x &= x - 1
		return ans

class ST:

	def __init__(self, arr):
		n = len(arr)
		mx = n.bit_length()
		self.st = [[0] * mx for i in range(n)]
		for i in range(n):
			self.st[i][0] = arr[i]
		for j in range(1, mx):
			for i in range(n - (1 << j) + 1):
				self.st[i][j] = max(self.st[i][j - 1], self.st[i + (1 << j - 1)][j - 1])

	def query(self, l, r):
		if l > r:
			return -inf
		s = (r + 1 - l).bit_length() - 1
		return max(self.st[l][s], self.st[r - (1 << s) + 1][s])

class UFS:

	def __init__(self, n):
		self.parent = [i for i in range(n)]
		self.ranks = [0] * n

	def find(self, x):
		if x != self.parent[x]:
			self.parent[x] = self.find(self.parent[x])
		return self.parent[x]

	def union(self, u, v):
		(pu, pv) = (self.find(u), self.find(v))
		if pu == pv:
			return False
		if self.ranks[pu] >= self.ranks[pv]:
			self.parent[pv] = pu
			if self.ranks[pv] == self.ranks[pu]:
				self.ranks[pu] += 1
		else:
			self.parent[pu] = pv

def Prime(n):
	c = 0
	prime = []
	flag = [0] * (n + 1)
	for i in range(2, n + 1):
		if not flag[i]:
			prime.append(i)
			c += 1
		for j in range(c):
			if i * prime[j] > n:
				break
			flag[i * prime[j]] = prime[j]
			if i % prime[j] == 0:
				break
	return (flag, prime)

def dij(s, graph):
	d = {}
	d[s] = 0
	heap = [(0, s)]
	seen = set()
	while heap:
		(dis, u) = heappop(heap)
		if u in seen:
			continue
		seen.add(u)
		for (v, w) in graph[u]:
			if v not in d or d[v] > d[u] + w:
				d[v] = d[u] + w
				heappush(heap, (d[v], v))
	return d

def bell(s, g):
	dis = AI(n, inf)
	dis[s] = 0
	for i in range(n - 1):
		for (u, v, w) in edge:
			if dis[v] > dis[u] + w:
				dis[v] = dis[u] + w
	change = A(n)
	for i in range(n):
		for (u, v, w) in edge:
			if dis[v] > dis[u] + w:
				dis[v] = dis[u] + w
				change[v] = 1
	return dis

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

def lis(nums):
	res = []
	for k in nums:
		i = bisect.bisect_left(res, k)
		if i == len(res):
			res.append(k)
		else:
			res[i] = k
	return len(res)

def RP(nums):
	n = len(nums)
	s = set(nums)
	d = {}
	for (i, k) in enumerate(sorted(s), 1):
		d[k] = i
	bi = BIT([0] * (len(s) + 1))
	ans = 0
	for i in range(n - 1, -1, -1):
		ans += bi.query(d[nums[i]] - 1)
		bi.update(d[nums[i]], 1)
	return ans

class DLN:

	def __init__(self, val):
		self.val = val
		self.pre = None
		self.next = None

def nb(i, j, n, m):
	for (ni, nj) in [[i + 1, j], [i - 1, j], [i, j - 1], [i, j + 1]]:
		if 0 <= ni < n and 0 <= nj < m:
			yield (ni, nj)

def topo(n):
	q = deque()
	res = []
	for i in range(1, n + 1):
		if ind[i] == 0:
			q.append(i)
			res.append(i)
	while q:
		u = q.popleft()
		for v in g[u]:
			ind[v] -= 1
			if ind[v] == 0:
				q.append(v)
				res.append(v)
	return res

@bootstrap
def gdfs(r, p):
	if len(g[r]) == 1 and p != -1:
		yield None
	for ch in g[r]:
		if ch != p:
			yield gdfs(ch, r)
	yield None
t = N()
for i in range(t):
	(n, k) = RL()
	a = RLL()
	s = set(a)
	for i in range(n + 1):
		if i not in s:
			mex = i
			break
	ma = max(a)
	if k == 0:
		ans = len(s)
	elif mex < ma:
		s.add((mex + ma + 1) // 2)
		ans = len(s)
	else:
		ans = len(s) + k
	print(ans)


import math

def mexMax(n, k, array):
	s = set(array)
	m = len(s)
	for x in range(m + 1):
		if x not in s:
			mex = x
			break
	maxi = max(s)
	if mex < maxi and k > 0:
		s.add(math.ceil((mex + maxi) / 2))
		return len(s)
	else:
		return len(s) + k
t = int(input())
final = []
for _ in range(t):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	final.append(mexMax(n, k, l))
for _ in range(t):
	print(final[_])


import sys
from itertools import accumulate
import os
from io import BytesIO, IOBase
from math import ceil
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')
T = int(input())
for _ in range(T):
	(n, k) = map(int, input().split())
	arr = sorted(map(int, input().split()))
	seq = list(range(n))
	if arr == seq:
		print(n + k)
		continue
	(mex, max_) = (None, arr[-1])
	for i in range(n):
		if arr[i] != i:
			mex = i
			break
	if mex is None:
		mex = n
	arr = set(arr)
	go = min(10, k)
	for _ in range(go):
		val = ceil((mex + max_) / 2)
		arr.add(val)
		max_ = max(arr)
	print(len(arr))


def mex(l):
	s = set(l)
	z = 0
	for i in range(max(l) + 2):
		if i not in s:
			z = i
			break
	return z
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	l = list(map(int, input().split()))
	s = set(l)
	if mex(l) == max(l) + 1:
		print(a + b)
		continue
	if b > 0:
		s.add((max(l) + mex(l) + 1) // 2)
	print(len(s))


import sys
from math import ceil

def find_mex(nums, start):
	while start in nums:
		start += 1
	return start

def perform(length, nums, k):
	if k == 0:
		return length
	max_ = max(nums)
	if max_ == length - 1:
		return length + k
	mex_ = find_mex(nums, 0)
	new_elem = ceil((mex_ + max_) / 2)
	nums.add(new_elem)
	return len(nums)
n = int(sys.stdin.readline().strip())
ans = 0
for i in range(n):
	line = sys.stdin.readline().strip()
	values = list(map(int, line.split()))
	(n, k) = values
	line = sys.stdin.readline().strip()
	multi_set = set(map(int, line.split()))
	res = perform(len(multi_set), multi_set, k)
	print(res)


from math import ceil
from bisect import bisect_left
for i in range(int(input())):
	(n, k) = map(int, input().split())
	spic = sorted(list(map(int, input().split())))
	maxs = spic[-1]
	mex = 0
	try:
		while mex == spic[bisect_left(spic, mex)]:
			mex += 1
	except IndexError:
		pass
	if mex == maxs + 1:
		print(n + k)
		continue
	r = ceil((mex + maxs) / 2)
	if k > 0:
		spic.insert(bisect_left(spic, r), r)
	print(len(set(spic)))


import math
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	s = set(l)
	if k == 0:
		print(len(s))
		continue
	for i in range(0, n + 1):
		if i not in s:
			mex = i
			break
	max1 = max(s)
	if mex > max1:
		print(len(s) + k)
	else:
		s.add(math.ceil((max1 + mex) / 2))
		print(len(s))


def zip_sorted(a, b):
	(a, b) = zip(*sorted(zip(a, b)))
	sorted(zip(a, b), key=lambda x: x[1])
	return (a, b)

def number_to_list(a):
	b = []
	while a >= 1:
		c = a % 10
		a = int(a / 10)
		b.append(c)
	return list(reversed(b))

def str_list_to_int_list(a):
	a = list(map(int, a))
	return a

def make_1d_array(n, inti=0):
	a = [inti for _ in range(n)]
	return a

def make_2d_array(n, m, inti=0):
	a = [[inti for _ in range(m)] for _ in range(n)]
	return a

def make_3d_array(n, m, k, inti=0):
	a = [[[inti for _ in range(k)] for _ in range(m)] for _ in range(n)]
	return a

def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
import sys
import math
from collections import defaultdict
input = sys.stdin.readline
I = lambda : list(map(int, input().split()))
S = lambda : list(map(str, input()))
(t,) = I()
for t1 in range(t):
	(n, k) = I()
	a = I()
	a = sorted(list(set(a)))
	if k == 0:
		print(len(a))
	else:
		mex = -1
		max1 = max(a)
		count = 0
		for i in range(len(a)):
			if i != a[i] and count == 0:
				mex = i
				count = 1
				break
		if mex == -1:
			mex = len(a)
		if mex > max1:
			print(len(a) + k)
		elif math.ceil((mex + max1) / 2) in a:
			print(len(a))
		else:
			print(len(a) + 1)


def main():
	for _ in range(int(input())):
		(n, k) = map(int, input().split())
		l = sorted(map(int, input().split()))
		for (i, a) in enumerate(l):
			if a != i:
				if k:
					k = (i + l[-1] + 1) // 2 not in l
				break
		print(n + k)
main()


R = lambda : map(int, input().split())
(t,) = R()
exec(t * 'n,k=R();a={*R()};i=0\nwhile{i}&a:i+=1\nprint(n+(k>0)*(k,i+max(a)+1>>1not in a)[i<n])\n')


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	setArr = list(set(arr))
	if k == 0:
		print(len(setArr))
		continue
	setArr.sort()
	f = 1
	mex = -1
	for i in range(len(setArr)):
		if setArr[i] == i:
			pass
		else:
			f = 0
			mex = i
			break
	from math import ceil
	if f == 1:
		print(len(setArr) + k)
	elif ceil((setArr[-1] + mex) / 2) in setArr:
		print(len(setArr))
	else:
		print(len(setArr) + 1)


def mex(check):
	x = 0
	while x in check:
		x += 1
	return x
t = int(input())
otv = []
for p in range(t):
	(n, k) = map(int, input().split())
	mass = set(list(map(int, input().split())))
	if k == 0:
		otv.append(n)
		continue
	else:
		b = max(mass)
		a = mex(mass)
		addition = (a + b + 1) // 2
		if addition > b:
			otv.append(n + k)
		else:
			mass.add(addition)
			otv.append(len(mass))
for j in otv:
	print(j)


import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
MOD = 10 ** 9 + 7

def solve():
	(n, k) = map(int, input().split())
	A = list(map(int, input().split()))
	if k == 0:
		print(n)
		return
	set_A = set(A)
	if set_A == set(list(range(n))):
		print(n + k)
	else:
		max_a = max(A)
		mex = 0
		while mex in set_A:
			mex += 1
		set_A.add((max_a + mex + 1) // 2)
		print(len(set_A))
t = int(input())
for _ in range(t):
	solve()


import math
for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	array = set(map(int, input().split()))
	if k == 0:
		print(n)
		continue
	maxx = max(array)
	for i in range(0, maxx + 2):
		if i not in array:
			mexx = i
			break
	newEle = math.ceil((maxx + mexx) / 2)
	if newEle == mexx:
		print(len(array) + k)
	else:
		array.add(newEle)
		print(len(array))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	(s, mex_num) = (set([int(x) for x in input().split()]), 0)
	if k:
		while mex_num in s:
			mex_num += 1
		max_num = max(s)
		num_to_add = (max_num + mex_num + 1) // 2
		if num_to_add != mex_num:
			s.add(num_to_add)
			k = 0
	print(len(s) + k)


for __ in range(int(input())):
	(n, k) = map(int, input().split())
	s = set(map(int, input().split()))
	stat = 0
	mesh = max_ = max(s)
	if k == 0:
		print(len(s))
		continue
	for i in range(max_):
		if i not in s:
			mesh = i
			stat = 1
			break
	v = mesh + max_
	if v % 2 == 0:
		v = v // 2
	else:
		v = v // 2 + 1
	if stat:
		res = len(s)
		if v not in s:
			res += 1
	else:
		res = len(s) + k
	print(res)


import math, sys
input = sys.stdin.readline

def mex(x):
	i = 0
	while i in x:
		i += 1
	return i
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	numbers = set([int(i) for i in input().split()])
	if not k:
		print(n)
	elif mex(numbers) == max(numbers) + 1:
		print(n + k)
	else:
		numbers.add(math.ceil((max(numbers) + mex(numbers)) / 2))
		print(len(numbers))


import math
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	elem = set(map(int, input().split()))

	def max_mex(elements, n, k):
		original_len = len(elements)
		for i in range(len(elements) + 1):
			if i not in elements:
				a = max(elements)
				b = i
				if a < b:
					return n + k
				elif k == 0:
					return len(elements)
				else:
					for j in range(k):
						result = math.ceil((a + b) / 2)
						elements.add(result)
						if original_len == len(elements):
							return len(elements)
						elif j == k - 1:
							return len(elements)
						original_len = len(elements)
	print(max_mex(elem, n, k))


import collections
import string
import math
import copy
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))

def input():
	return sys.stdin.readline().rstrip('\r\n')
mo = 998244353

def exgcd(a, b):
	if not b:
		return (1, 0)
	(y, x) = exgcd(b, a % b)
	y -= a // b * x
	return (x, y)

def getinv(a, m):
	(x, y) = exgcd(a, m)
	return -1 if x == 1 else x % m

def comb(n, b):
	res = 1
	b = min(b, n - b)
	for i in range(b):
		res = res * (n - i) * getinv(i + 1, mo) % mo
	return res % mo

def quickpower(a, n):
	res = 1
	while n:
		if n & 1:
			res = res * a % mo
		n >>= 1
		a = a * a % mo
	return res

def dis(a, b):
	return abs(a[0] - b[0]) + abs(a[1] - b[1])

def getpref(x):
	if x > 1:
		return x * (x - 1) >> 1
	else:
		return 0

def orafli(upp):
	primes = []
	marked = [False for i in range(upp + 3)]
	prvs = [i for i in range(upp + 3)]
	for i in range(2, upp):
		if not marked[i]:
			primes.append(i)
		for j in primes:
			if i * j >= upp:
				break
			marked[i * j] = True
			prvs[i * j] = j
			if i % j == 0:
				break
	return (primes, prvs)

def lower_ord(c: str) -> int:
	return ord(c) - 97

def upper_ord(c: str) -> int:
	return ord(c) - 65

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

def read_int():
	s = input().split()
	if len(s) == 1:
		return int(s[0])
	else:
		return map(int, s)

def ask(s):
	print(f'? {s}', flush=True)

def answer(s):
	print(f'! {s}', flush=True)

def solve():
	(n, k) = read_int()
	li = read_list()
	s = set(li)
	if k == 0:
		print(n)
		return
	f = True
	for i in range(n):
		if i not in s:
			f = False
			tx = i
			s.add(math.ceil((tx + max(s)) / 2))
			print(len(s))
			return
	print(n + k)
t = int(input())
for ti in range(t):
	solve()


import math
import sys
t = int(sys.stdin.readline())
for i1 in range(t):
	(n, k) = map(int, sys.stdin.readline().split())
	l = list(map(int, sys.stdin.readline().split()))
	flag = 0
	if k == 0:
		sys.stdout.write(str(len(set(l))) + '\n')
		continue
	i = 0
	l.sort()
	for j1 in l:
		if j1 != i:
			flag = 1
			break
		i += 1
	if flag == 1:
		if math.ceil((max(l) + i) / 2) in l:
			sys.stdout.write(str(len(set(l))) + '\n')
		else:
			sys.stdout.write(str(len(set(l)) + 1) + '\n')
	if flag == 0:
		k1 = len(set(l)) + k
		sys.stdout.write(str(k1) + '\n')


def rUp(a):
	if int(a) == a:
		return a
	return int(a) + 1

def mex(s):
	a = 0
	while True:
		if a in s:
			a += 1
		else:
			return a
t = int(input())
for _ in range(t):
	(n, k) = input().split()
	(n, k) = (int(n), int(k))
	mset = set(map(int, input().split()))
	if k == 0:
		print(n)
		continue
	M = max(mset)
	m = mex(mset)
	if m > M:
		print(n + k)
		continue
	if rUp((M + m) / 2) in mset:
		pass
	else:
		n += 1
	print(n)


import sys
input = sys.stdin.readline
for TEST in range(int(input())):
	(n, k) = map(int, input().split())
	s = [*map(int, input().split())]
	if k == 0:
		print(n)
		continue
	s_set = set(s)
	(mex, M, g, flag) = (0, 0, 0, 0)
	while mex in s_set:
		mex += 1
	M = max(s)
	if mex + M & 1:
		g = (mex + M + 1) // 2
	else:
		g = (mex + M) // 2
	if g in s_set:
		flag = 1
	s_set.add(g)
	mex = 0
	while mex in s_set:
		mex += 1
	if mex > M:
		print(n + k)
	else:
		print(n + 1 - flag)


import math
from collections import defaultdict
from sys import stdin
input = stdin.readline
T = int(input())
for _ in range(T):
	(n, op) = map(int, input().split())
	arr = list(map(int, input().split()))
	s = set()
	for i in arr:
		s.add(i)
	c = 0
	while True:
		if c not in s:
			mexi = c
			break
		c += 1
	maxi = max(arr)
	if mexi > maxi:
		print(len(s) + op)
		continue
	mid = (maxi + mexi + 2 - 1) // 2
	if mid in s:
		print(len(s))
	else:
		print(len(s) + min(op, 1))


import sys
input = sys.stdin.readline

def main():
	t = int(input())
	for _ in range(t):
		(N, K) = [int(x) for x in input().split()]
		A = [int(x) for x in input().split()]
		A_set = set(A)
		if K == 0:
			print(len(A_set))
			continue
		mex = 0
		for i in range(10 ** 5 + 2):
			if i in A_set:
				continue
			else:
				mex = i
				break
		ma = max(A)
		if mex - ma == 1:
			print(len(A_set) + K)
		else:
			A_set.add(-(-(mex + ma) // 2))
			print(len(A_set))
main()


import math
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	set_ = set(map(int, input().split()))
	max_ = max(set_)
	mex = 0
	while mex in set_:
		mex += 1
	if k == 0:
		print(n)
	elif max_ == mex - 1:
		print(n + k)
	else:
		set_.add(math.ceil((max_ + mex) / 2))
		print(len(set_))


from bisect import bisect_left
T = int(input())
for _ in range(T):
	(N, K) = [int(v) for v in input().split()]
	if not K:
		input()
		print(N)
		continue
	a = [int(v) for v in input().split()]
	a.sort()
	if a[-1] == N - 1:
		print(N + K)
		continue
	for (i, v) in enumerate(a):
		if v != i:
			t = i + a[-1] + 1 >> 1
			if t == a[bisect_left(a, t)]:
				print(N)
			else:
				print(N + 1)
			break


from math import ceil
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s1 = set((int(x) for x in input().split()))
	s1 = sorted(s1)
	flag = 0
	for (id, val) in enumerate(s1):
		if id != val:
			flag = 1
			break
	mex = id if flag == 1 else id + 1
	maxs = max(s1)
	term = ceil((maxs + mex) / 2)
	if term <= maxs:
		if term in s1 or k == 0:
			print(len(s1))
		else:
			print(len(s1) + 1)
	else:
		print(len(s1) + k)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	ls = list(map(int, input().split()))
	ans = None
	for turn in range(k):
		s = set(ls)
		non_ls = list(s)
		max_num = max(s)
		mex_num = None
		for m in range(0, max_num + 2):
			if m not in s:
				mex_num = m
				break
		if mex_num == max_num + 1:
			ans = len(s) + k
			break
		else:
			if (max_num + mex_num) % 2 == 0:
				half = (max_num + mex_num) // 2
			else:
				half = (max_num + mex_num + 1) // 2
			if half in s:
				ans = len(s)
				break
			else:
				ls.append(half)
	if ans == None:
		print(len(set(ls)))
	else:
		print(ans)


def mex(s, mi, mx):
	if len(s) == mx + 1:
		return mx + 1
	for i in range(mi, mx + 2):
		if i not in s:
			return i
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = set(map(int, input().split()))
	mx = max(s)
	mex_v = mex(s, 0, mx)
	flag = 0
	while k > 0:
		k -= 1
		alp = (mex_v + mx + 1) // 2
		s.add(alp)
		if alp <= mx and alp > mex_v:
			break
		elif mex_v == mx + 1:
			flag = 1
			print(len(s) + k)
			break
		else:
			if alp > mx:
				mx = alp
			mex_v = mex(s, mex_v, mx)
	if flag == 0:
		print(len(s))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = set(map(int, input().split()))
	m = max(a)
	mex = 0
	while mex in a:
		mex += 1
	if mex > m or k == 0:
		print(n + k)
	elif (m + mex + 1) // 2 in a:
		print(n)
	else:
		print(n + 1)


from __future__ import division, print_function
import os, sys
from io import BytesIO, IOBase
if sys.version_info[0] < 3:
	from __builtin__ import xrange as range
	from future_builtins import ascii, filter, hex, map, oct, zip

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

def fi():
	return float(input())

def si():
	return input()

def msi():
	return map(str, input().split())

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

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

def lsi():
	return list(msi())

def read():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def lcm(x, y):
	return x * y // gcd(x, y)
mod = 1000000007

def modInverse(b, m):
	g = gcd(b, m)
	if g != 1:
		return -1
	else:
		return pow(b, m - 2, m)

def ceil(x, y):
	if x % y == 0:
		return x // y
	else:
		return x // y + 1

def modu(a, b, m):
	a = a % m
	inv = modInverse(b, m)
	if inv == -1:
		return -999999999
	else:
		return inv * a % m
from math import log, factorial, cos, tan, sin, radians, floor, sqrt, log2
import bisect
import random
import string
from decimal import *
getcontext().prec = 50
abc = 'abcdefghijklmnopqrstuvwxyz'
pi = 3.141592653589793

def gcd1(a):
	if len(a) == 1:
		return a[0]
	ans = a[0]
	for i in range(1, len(a)):
		ans = gcd(ans, a[i])
	return ans

def mykey(x):
	return (x[1], -x[0])

def main():
	for _ in range(ii()):
		(n, k) = mi()
		a = li()
		mex = -1
		d = dict()
		for i in a:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		for i in range(0, 10 ** 5 + 1):
			if i not in d:
				mex = i
				break
		mx = max(a)
		if mex != mx + 1:
			y = ceil(mex + mx, 2)
			if y not in d:
				ans = n + min(k, 1)
			else:
				ans = n
		else:
			ans = n + k
		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')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


t = int(input())

def mex(s):
	for i in range(len(s)):
		if i != s[i]:
			return i
	return len(s)
for _ in range(t):
	(n, k) = map(int, input().split())
	s = list(map(int, input().split()))
	s.sort()
	a = mex(s)
	b = max(s)
	c = (a + b + 1) // 2
	result = n
	if a < b:
		if k > 0 and c not in s:
			result = n + 1
	else:
		result = n + k
	print(result)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	l = set(map(int, input().split()))
	c = len(l)
	m = max(l)
	p = -1
	if k == 0:
		print(c)
		continue
	for i in range(m + 1):
		if i not in l:
			p = i
			break
	if p == -1:
		print(c + k)
	else:
		x = p + m
		y = 0
		if x % 2 != 0:
			y = x // 2 + 1
		else:
			y = x // 2
		if y not in l:
			print(c + 1)
		else:
			print(c)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	if k == 0:
		print(n)
	else:
		arr.sort()
		mex = -1
		max = arr[-1]
		for i in range(n):
			if i != arr[i]:
				mex = i
				break
		if mex == -1:
			print(n + k)
		else:
			ans = n
			while k:
				new = (mex + max) / 2
				if new != int(new):
					new = int(new) + 1
				else:
					new = int(new)
				if new in arr:
					break
				else:
					arr.append(new)
					ans += 1
			print(ans)


I = lambda : map(int, input().split())
for i in '*' * int(input()):
	(n, k) = I()
	a = set(I())
	while k > 0:
		q = 0
		while q in a:
			q += 1
		w = max(a)
		if q == w + 1:
			break
		e = (w + q + 1) // 2
		if e in a:
			k = 0
		else:
			a.add(e)
		k -= 1
	print(len(a) + max(k, 0))


import math

def mex(a):
	for i in range(len(a) + 1):
		if i not in a:
			return i
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = set(map(int, input().split()))
	if mex(a) > max(a):
		print(n + k)
		continue
	elif k > 0:
		a.add(math.ceil((max(a) + mex(a)) / 2))
	print(len(a))


import sys
import math
input = sys.stdin.readline
for _ in range(int(input())):
	(n, k) = [int(i) for i in input().split()]
	a = sorted([int(i) for i in input().split()])
	if a == list(range(n)):
		print(n + k)
	else:
		c = 0
		for i in a:
			if i != c:
				break
			c += 1
		c = int(math.ceil((c + a[-1]) / 2))
		a = set(a)
		if k:
			a.add(c)
		print(len(a))


import math
import itertools as it
x = int(input())
for i in range(x):
	(n, k) = map(int, input().split())
	s = [int(s) for s in input().split()]
	if k > 0:
		myset = set(s)
		minn = next((i for i in it.count() if i not in myset))
		if minn > max(s):
			print(n + k)
		elif max(s) - minn > 1:
			if math.ceil((max(s) + minn) / 2) not in s:
				print(n + 1)
			else:
				print(n)
		else:
			print(n)
	else:
		print(n)


class Solution:

	def __init__(self):
		pass

	def findMEX(self, S):
		N = len(S)
		newArr = sorted([ele for ele in S if ele < N])
		n = len(newArr)
		for i in range(n):
			if newArr[i] != i:
				return i
		return n

	def distictElementAfterK(self, S, k):
		if k == 0:
			return len(S)
		(mex, maxi, ans) = (self.findMEX(S), max(S), len(S))
		if mex > maxi:
			ans += k
		else:
			newEle = round((mex + maxi) / 2 + 0.01)
			if newEle not in S:
				ans += 1
		return ans
t = int(input())
while t:
	(n, k) = map(int, input().split(' '))
	S = set(map(int, input().split(' ')))
	s = Solution()
	print(s.distictElementAfterK(S, k))
	t -= 1


t = int(input())
for _i in range(t):
	(n, k) = map(int, input().split(' '))
	a = list(map(int, input().split(' ')))
	a.sort()
	minA = 0
	for i in a:
		if minA == i:
			minA += 1
		else:
			break
	maxA = max(a)
	a = set(a)
	if minA == maxA + 1:
		print(k + len(a))
	else:
		if k > 0:
			a.add((minA + maxA + 1) // 2)
		print(len(a))


ll = lambda : map(int, input().split())
t = lambda : int(input())
ss = lambda : input()
lx = lambda x: map(int, input().split(x))
from math import log10, log2, ceil, factorial as f, gcd
for _ in range(t()):
	(n, k) = ll()
	a = list(ll())
	s = sorted(set(a))
	flag = -1
	x = max(s)
	for i in range(len(s)):
		if s[i] != i:
			flag = i
			break
	if flag == -1:
		print(len(s) + k)
	elif k > 0 and ceil((x + flag) / 2) not in s:
		print(len(s) + 1)
	else:
		print(len(s))


import sys
import math
input = sys.stdin.readline
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = list(map(int, input().split()))
	ans = len(set(s))
	if not k:
		print(ans)
		continue
	s.sort()
	s_max = s[-1]
	s_mex = n
	for i in range(n):
		if i != s[i]:
			s_mex = i
			break
	if s_mex > s_max:
		ans += k
	elif math.ceil((s_max + s_mex) / 2) not in s:
		ans += 1
	print(ans)


import math
t = int(input())
for i in range(t):
	l = list(map(int, input().rstrip().split()))
	n = l[0]
	k = l[1]
	l1 = list(map(int, input().rstrip().split()))
	l1.sort()
	count = 0
	c = 0
	for m in range(len(l1)):
		if l1[m] == m:
			count += 1
			if count == len(l1):
				print(n + k)
		else:
			a = max(l1)
			for x in range(0, a + 2):
				if l1.count(x) == 0:
					b = x
					break
			for j in range(k):
				a = max(l1)
				if math.ceil((a + b) / 2) != c:
					c = math.ceil((a + b) / 2)
					l1.append(c)
				else:
					break
			s = set(l1)
			print(len(s))
			break


def mex(arr):
	s = set(arr)
	z = 0
	for i in range(max(arr) + 2):
		if i not in s:
			z = i
			break
	return z
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	s = set(arr)
	if mex(arr) == max(arr) + 1:
		print(n + k)
		continue
	if k > 0:
		s.add((max(arr) + mex(arr) + 1) // 2)
	print(len(s))


from collections import defaultdict, OrderedDict, Counter
from sys import stdin, stdout
from bisect import bisect_left, bisect_right
from queue import Queue, PriorityQueue
from heapq import *
from statistics import *
from math import *
import fractions
import copy
from copy import deepcopy
import sys
import io
sys.setrecursionlimit(10000)
import math
import os
import bisect
import collections
mod = pow(10, 9) + 7
import random
from random import random, randint, randrange
from time import time

def ncr(n, r, p=mod):
	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 normalncr(n, r):
	r = min(r, n - r)
	count = 1
	for i in range(n - r, n + 1):
		count *= i
	for i in range(1, r + 1):
		count //= i
	return count
inf = float('inf')
adj = defaultdict(set)
visited = defaultdict(int)

def addedge(a, b):
	adj[a].add(b)
	adj[b].add(a)

def bfs(v):
	q = Queue()
	q.put(v)
	visited[v] = 1
	while q.qsize() > 0:
		s = q.get_nowait()
		print(s)
		for i in adj[s]:
			if visited[i] == 0:
				q.put(i)
				visited[i] = 1

def dfs(v, visited):
	if visited[v] == 1:
		return
	visited[v] = 1
	print(v)
	for i in adj[v]:
		dfs(i, visited)

def reverse_bisect_right(a, x, lo=0, hi=None):
	if lo < 0:
		raise ValueError('lo must be non-negative')
	if hi is None:
		hi = len(a)
	while lo < hi:
		mid = (lo + hi) // 2
		if x > a[mid]:
			hi = mid
		else:
			lo = mid + 1
	return lo

def reverse_bisect_left(a, x, lo=0, hi=None):
	if lo < 0:
		raise ValueError('lo must be non-negative')
	if hi is None:
		hi = len(a)
	while lo < hi:
		mid = (lo + hi) // 2
		if x >= a[mid]:
			hi = mid
		else:
			lo = mid + 1
	return lo

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

def get_str_list_in_int():
	return [int(i) for i in list(input())]

def get_str_list():
	return list(input())

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

def input_int():
	return int(input())

def matrix(a, b):
	return [[0 for i in range(b)] for j in range(a)]

def swap(a, b):
	return (b, a)

def find_gcd(l):
	a = l[0]
	for i in range(len(l)):
		a = gcd(a, l[i])
	return a

def is_prime(n):
	sqrta = int(sqrt(n))
	for i in range(2, sqrta + 1):
		if n % i == 0:
			return 0
	return 1

def prime_factors(n):
	sqrta = int(sqrt(n))
	for i in range(2, sqrta + 1):
		if n % i == 0:
			return [i] + prime_factors(n // i)
	return [n]

def p(a):
	if type(a) == str:
		print(a + '\n')
	else:
		print(str(a) + '\n')

def ps(a):
	if type(a) == str:
		print(a)
	else:
		print(str(a))

def kth_no_not_div_by_n(n, k):
	return k + (k - 1) // (n - 1)

def forward_array(l):
	n = len(l)
	stack = []
	forward = [0] * n
	for i in range(len(l) - 1, -1, -1):
		while len(stack) and l[stack[-1]] < l[i]:
			stack.pop()
		if len(stack) == 0:
			forward[i] = len(l)
		else:
			forward[i] = stack[-1]
		stack.append(i)
	return forward

def backward_array(l):
	n = len(l)
	stack = []
	backward = [0] * n
	for i in range(len(l)):
		while len(stack) and l[stack[-1]] < l[i]:
			stack.pop()
		if len(stack) == 0:
			backward[i] = -1
		else:
			backward[i] = stack[-1]
		stack.append(i)
	return backward
nc = 'NO'
yc = 'YES'
ns = 'No'
ys = 'Yes'

def mexa(l):
	s = set(l)
	for i in range(len(l) + 1):
		if i not in s:
			return i

def all_pre(l):
	s = set(l)
	for i in range(len(l) + 1):
		if i not in s:
			break
	if i == len(l):
		return 1
	return 0
for i in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	if k == 0:
		print(n)
		continue
	pre_mex = mexa(l)
	pre_max = max(l)
	if pre_mex > pre_max:
		print(n + k)
		continue
	adder = pre_max + pre_mex
	adder = ceil(adder / 2)
	if adder in l:
		print(n)
	else:
		print(n + 1)


def main():
	import math
	ans = []
	t = int(input())
	for _ in range(t):
		(n, k) = map(int, input().split())
		a = list(map(int, input().split()))
		a.sort()
		if k == 0:
			ans.append(n)
		elif a[-1] == n - 1:
			ans.append(n + k)
		else:
			mex = 0
			for x in a:
				if x == mex:
					mex += 1
				else:
					break
			s = set(a)
			x = math.ceil((mex + a[-1]) / 2)
			if x in s:
				ans.append(n)
			else:
				ans.append(n + 1)
	print('\n'.join(map(str, ans)))
main()


import sys, os.path
import math
import collections

def findMex(arr):
	for i in range(len(arr)):
		if arr[i] != i:
			return i
	return arr[-1] + 1

def solve():
	(n, k) = [int(i) for i in input().split()]
	arr = [int(i) for i in input().split()]
	if k == 0:
		print(n)
		return
	arr.sort()
	mexV = findMex(arr)
	maxV = arr[-1]
	if mexV == maxV + 1:
		print(n + k)
	else:
		print(n + (1 if math.ceil((maxV + mexV) / 2) not in arr else 0))
if os.path.exists('input_file.txt'):
	sys.stdin = open('input_file.txt', 'r')
	sys.stdout = open('output_file.txt', 'w')
n = 1
n = int(input())
for _ in range(n):
	solve()


import math
for t in range(int(input())):
	(n, k) = map(int, input().split())
	nums = set(map(int, input().split()))
	mexn = 0
	while mexn in nums:
		mexn += 1
	maxn = max(nums)
	if mexn > maxn or k == 0:
		print(n + k)
	else:
		print(n if math.ceil((mexn + maxn) / 2) in nums else n + 1)


import math

def max_mex(num):
	main_set = set(num)
	check_set = set([x for x in range(n)])
	a = check_set.difference(main_set)
	b = max(num)
	return math.ceil((a + b) / 2)
test_case = int(input())
for i in range(test_case):
	(n, k) = [int(x) for x in input().split()]
	num = [int(x) for x in input().split()]
	main_set = set(num)
	check_set = set([x for x in range(len(main_set))])
	a = check_set.difference(main_set)
	b = max(num)
	if k == 0:
		print(len(main_set))
	elif a == set():
		print(len(main_set) + k)
	else:
		a = min(a)
		new_num = math.ceil((a + b) / 2)
		if new_num in num:
			print(len(main_set))
		else:
			print(len(main_set) + 1)


import math

def get_mex(sett, last):
	for i in range(last, 10 ** 9 + 1):
		if i not in sett:
			return i

def solve(A, k):
	sett = set()
	for a in A:
		sett.add(a)
	mexx = get_mex(sett, 0)
	maxx = max(A)
	for i in range(k):
		if maxx + 1 == mexx:
			return len(sett) + (k - i)
		next = math.ceil((mexx + maxx) / 2)
		if next in sett:
			return len(sett)
		else:
			sett.add(next)
			mexx = get_mex(sett, mexx)
	return len(sett)
x = int(input())
for _ in range(x):
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	print(solve(B, A[1]))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = sorted(list(map(int, input().split())))
	if a[-1] - a[0] + 1 == n and a[0] == 0:
		print(n + k)
	else:
		if k == 0:
			print(n)
			continue
		j = 0
		for i in range(n):
			if a[i] != j:
				mes = j
				break
			j += 1
		if (a[-1] + mes + 1) // 2 in a:
			print(n)
		else:
			print(n + 1)


from collections import defaultdict, deque, Counter
from sys import stdin, stdout
from heapq import heappush, heappop
import math
import io
import os
import math
import bisect

def isPrime(x):
	for i in range(2, x):
		if i * i > x:
			break
		if x % i == 0:
			return False
	return True

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 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 * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime

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

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

def mapin():
	return map(int, input().split())
t = int(input())
for _ in range(t):
	(n, k) = mapin()
	l = [int(x) for x in input().split()]
	nn = 0
	l.sort()
	for i in l:
		if i == nn:
			nn += 1
	if nn > l[-1]:
		print(l[-1] + 1 + k)
	else:
		if k > 0:
			l.append(math.ceil((nn + l[-1]) / 2))
		print(len(set(l)))


import math

def mex(S, i):
	while i in S:
		i += 1
	return i
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	S = set(map(int, input().split()))
	a = mex(S, 0)
	b = max(S)
	if a == len(S):
		print(n + k)
	else:
		if k > 0:
			S.add(int(math.ceil((a + b) / 2)))
		print(len(S))


from math import ceil
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	num_list = list(map(int, input().split()))
	num_list.sort()
	MAX = num_list[-1]
	i = 0
	if k:
		for _ in num_list:
			if _ == i:
				pass
			else:
				MEX = i
				break
			i += 1
		if i == len(num_list):
			MEX = num_list[-1] + 1
		if MEX < MAX:
			num_list.append(ceil((MEX + MAX) / 2))
			print(len(set(num_list)))
		elif MEX > MAX:
			print(len(num_list) + k)
	else:
		print(len(num_list))


import sys
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	A = list(map(int, input().split()))
	A.sort()
	S = set(A)
	if A == list(range(n)):
		print(n + k)
		continue
	for (i, a) in enumerate(A):
		if i != a:
			mex = i
			break
	M = max(A)
	if k > 0:
		x = (mex + M + 1) // 2
		if x in S:
			print(len(S))
		else:
			print(len(S) + 1)
	else:
		print(len(S))


import sys
import math
import bisect
import heapq
from bisect import bisect_right
from sys import stdin, stdout

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

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

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

def get_list_of_list(n):
	return [list(map(int, sys.stdin.readline().strip().split())) for _ in range(n)]

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

def Solution(arr, n, k):
	mp = {}
	uniq = 0
	mx = max(arr)
	for v in arr:
		if v in mp:
			mp[v] += 1
		else:
			mp[v] = 1
		if mp[v] == 1:
			uniq += 1
	me = float('inf')
	for i in range(mx + 1):
		if not i in mp:
			me = i
			break
	if me < mx and k != 0:
		avg = math.ceil((me + mx) / 2)
		if avg in mp:
			mp[avg] += 1
		else:
			mp[avg] = 1
		if mp[avg] == 1:
			uniq += 1
	elif me > mx and k != 0:
		uniq += k
	print(uniq)

def main():
	for _ in range(get_int()):
		(n, k) = get_ints_in_variables()
		arr = get_ints_in_list()
		Solution(arr, n, k)
main()


t = int(input())
for i in range(0, t):
	f = input()
	array = f.split(' ')
	n = int(array[0])
	k = int(array[1])
	s = input()
	s = list(map(int, s.split(' ')))
	ss = set(s)
	for j in range(n + 1):
		if j not in ss:
			break
	MAX = max(ss)
	e = -(-(j + MAX) // 2)
	if len(ss) == MAX + 1:
		print(len(ss) + k)
	elif k >= 1 and e not in ss:
		print(len(ss) + 1)
	else:
		print(len(ss))


import sys
input = sys.stdin.readline

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

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

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

def ma():
	return map(int, input().split())
t = inp()
while t:
	t -= 1
	(n, k) = ma()
	a = lis()
	a.sort()
	p = 0
	for i in range(n):
		if a[i] == p:
			p += 1
		else:
			break
	if p == n:
		print(n + k)
		continue
	else:
		add = p + a[-1]
		add = (add - 1) // 2 + 1
		if add in a:
			print(n)
		elif k:
			print(n + 1)
		else:
			print(n)


from math import ceil
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = set(map(int, input().split()))
	if k == 0:
		print(len(l))
	else:
		for i in range(n):
			if i not in l:
				mex = i
				break
		else:
			mex = n
		if mex != n:
			if ceil((mex + max(l)) / 2) not in l:
				print(len(l) + 1)
			else:
				print(len(l))
		else:
			print(len(l) + k)


t = int(input())
while t:
	t -= 1
	(n, k) = map(int, input().split())
	A = list(map(int, input().split()))
	setA = set(A)
	ma_x = max(A)
	flag = 0
	if k == 0:
		print(n)
		continue
	for i in range(0, 999999999):
		if i not in setA:
			mex = i
			break
	if mex > ma_x:
		print(n + k)
	else:
		p = mex + ma_x
		if p % 2 != 0:
			p = p / 2 * 10
			if p % 10 >= 5:
				p = int(p // 10) + 1
			else:
				p = int(p // 10)
		else:
			p = p // 2
		if p not in setA:
			print(n + 1)
		else:
			print(n)


T = int(input())
r = 1
while r <= T:
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	dic = {}
	mex = 0
	maximum = 0
	for i in range(n):
		dic[arr[i]] = 1
		maximum = max(arr[i], maximum)
	while mex in dic:
		mex += 1
	if k == 0:
		print(len(dic))
	else:
		nextone = (mex + maximum + 1) // 2
		if nextone in dic:
			print(len(dic))
		elif mex > maximum:
			print(len(dic) + k)
		else:
			print(len(dic) + 1)
	r += 1


from sys import stdin, stdout
from collections import Counter, OrderedDict, defaultdict
import math
import re
cin = stdin.readline
cout = stdout.write
mp = lambda : list(map(int, cin().split()))

def chars():
	s = cin()
	return list(s[:len(s) - 1])

def pl(a):
	for val in a:
		cout(str(val) + ' ')
	cout('\n')

def binSearch(l, val, start, end):
	if end < start:
		return False
	mid = (start + end) // 2
	if l[mid] == val:
		return True
	elif l[mid] < val:
		return binSearch(l, val, mid + 1, end)
	elif l[mid] > val:
		return binSearch(l, val, start, mid - 1)

def myLog(x, y):
	z = int(math.log(x, y))
	if y ** (z + 1) > x:
		return z
	elif y ** (z + 1) == x:
		return z + 1
(t,) = mp()
for _ in range(t):
	(n, k) = mp()
	a = set(mp())
	a = sorted(list(a))
	x = 0
	for i in range(len(a)):
		if i != a[i]:
			x = i
			break
	else:
		x = max(a) + 1
	if not k:
		cout(str(len(a)) + '\n')
	elif max(a) + 1 == x:
		cout(str(len(a) + k) + '\n')
	else:
		a += [math.ceil((x + max(a)) / 2)]
		a = set(a)
		cout(str(len(a)) + '\n')


import sys
from sys import stdin
import math

def iinput():
	return int(input())

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

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

def fiinput():
	return int(stdin.readline())

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

def flinput():
	return list(map(int, stdin.readline().strip().split()))
c = 0
for _ in range(iinput()):
	(n, k) = minput()
	list1 = linput()
	m = max(list1)
	set1 = set(list1)
	f = 0
	if k != 0:
		list1.sort()
		x = 0
		for i in range(len(list1)):
			if list1[i] == x:
				x += 1
			elif list1[i] > x:
				f = 1
				ff = x
		if f == 1:
			set1.add(math.ceil((m + ff) / 2))
			print(len(set1))
		else:
			print(len(set1) + k)
	else:
		print(len(set1))


import math
t = int(input())
for i in range(t):
	(n, k) = input().split()
	n = int(n)
	k = int(k)
	s = set(map(int, input().split()))
	a = -1
	a = max(s)
	p = 0
	b = 0
	while b in s:
		b = b + 1
	ans = math.ceil((a + b) / 2)
	if k > 0:
		if a > b:
			if ans in s:
				print(n)
			else:
				print(n + 1)
		else:
			print(n + k)
	else:
		print(n)


from math import ceil

def find_mex(arr):
	mex = 0
	while True:
		if mex not in arr:
			return mex
		mex += 1

def find_max(arr):
	return max(arr)
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	lst = set(map(int, input().split()))
	a = find_max(lst)
	b = find_mex(lst)
	if b > a:
		print(len(lst) + k)
	elif k == 0:
		print(len(lst))
	else:
		ans = ceil((a + b) / 2)
		if ans in lst:
			print(len(lst))
		else:
			print(len(lst) + 1)


import sys, math, itertools, random, bisect
from collections import defaultdict
INF = sys.maxsize

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

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

def input():
	return sys.stdin.readline().strip()
mod = 10 ** 9 + 7
for _ in range(int(input())):
	(n, k) = get_ints()
	store = set()
	a = get_array()
	mx = -1
	for i in a:
		store.add(i)
		mx = max(mx, i)
	mex = -1
	for i in range(mx + 5):
		if i not in store:
			mex = i
			break
	x = math.ceil((mx + mex) / 2)
	if k == 0:
		print(n)
	elif mex > mx:
		print(n + k)
	elif x in store:
		print(n)
	else:
		print(n + 1)


from math import ceil
for tc in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	book = {}
	initlena = len(a)
	for i in a:
		if i not in book:
			book[i] = 1
	me = 0
	cnt = 0
	flag = 1
	ma = max(a)

	def mex(a):
		global me
		while me in book:
			me += 1
		return me
	while k > 0:
		m1 = mex(a)
		m2 = max(a)
		t = ceil((m1 + m2) / 2)
		if t in a:
			print(len(set(a)))
			flag = 0
			break
		if m1 == m2 + 1:
			print(m2 + k - cnt + 1)
			flag = 0
			break
		a.append(t)
		book[t] = 1
		cnt += 1
	if flag:
		print(len(set(a)))


for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	arr = set(map(int, input().split()))
	b = 0
	maxi = max(arr)
	for i in range(maxi + 1):
		if i not in arr:
			b = i
			break
	if len(arr) == maxi + 1:
		print(len(arr) + k)
	elif k >= 1:
		arr.add((b + maxi + 1) // 2)
		print(len(arr))
	else:
		print(len(arr))


import math
t = int(input())
while t:
	(n, k) = [int(x) for x in input().split()]
	l = set([int(x) for x in input().split()])
	ma = max(l)
	me = ma
	c = n
	for i in range(ma):
		if i not in l:
			me = i
			break
	if me == ma or k == 0:
		c = c + k
	else:
		x = math.ceil((ma + me) / 2)
		if x not in l:
			c = c + 1
	print(c)
	t = t - 1


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	s = set(a)
	mex = 0
	for i in range(n + 1):
		if i not in s:
			mex = i
			break
	l = len(s)
	m = max(a)
	b = (mex + m + 1) // 2
	if k == 0:
		print(l)
		continue
	if mex > m:
		print(l + k)
	else:
		if b not in s:
			l += 1
		print(l)


from math import ceil
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	if k == 0:
		print(len(set(a)))
	elif sorted(a) == [i for i in range(n)]:
		print(n + k)
	else:
		b = ceil((sorted(list(set([i for i in range(n)]) - set(a)))[0] + max(a)) / 2)
		if b in a:
			print(len(set(a)))
		else:
			print(len(set(a)) + 1)


from math import ceil
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = sorted(map(int, input().split()))
	Mex = -1
	if arr[0] != 0:
		Mex = 0
	else:
		for i in range(n - 1):
			if arr[i] != arr[i + 1] and arr[i] + 1 != arr[i + 1]:
				Mex = arr[i] + 1
				break
		else:
			Mex = arr[-1] + 1
	Max = arr[-1]
	S = set(arr)
	ans = len(S)
	if k > 0:
		if Max > Mex:
			S.add(ceil((Max + Mex) / 2))
			ans = len(S)
		elif Max < Mex:
			assert Mex == Max + 1
			ans += k
	print(ans)


import sys
input = lambda : sys.stdin.readline().rstrip()

def sol():
	if ls[0] == 0 and ls[-1] + 1 == n:
		return ls[-1] + k + 1
	max_ = ls[-1]
	prev = ls[0]
	if ls[0] != 0:
		mex_ = 0
	else:
		for idx in range(1, n):
			if ls[idx] == prev + 1:
				prev = ls[idx]
			else:
				mex_ = prev + 1
	S = set(ls)
	if k > 0:
		S.add((max_ + mex_ + 1) // 2)
		return len(S)
	else:
		return len(S)
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	ls = list(map(int, input().split()))
	ls.sort()
	print(sol())


t = int(input())

def mex(seq: set):
	res = 0
	while res in seq:
		res += 1
	return res
while t:
	inp = input().strip().split(' ')
	n = int(inp[0])
	k = int(inp[1])
	seq = [int(i) for i in input().strip().split(' ')]
	distinct = set(seq)
	ma = max(seq)
	me = mex(distinct)
	res = len(distinct)
	if k == 0:
		pass
	elif ma == me - 1:
		res += k
	elif (ma + me) // 2 + (ma + me) % 2 not in distinct:
		res += 1
	print(res)
	t -= 1


from math import ceil

def mex(se):
	me = max(se)
	check_for = 0
	while True:
		if check_for not in se:
			return check_for
		check_for += 1
for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	v = set(map(int, input().split()))
	if mex(v) > max(v):
		print(len(v) + k)
	elif k == 0:
		print(len(v))
	else:
		mx = max(v)
		mi = mex(v)
		addd = ceil((mx + mi) / 2)
		if addd not in v:
			print(len(v) + 1)
		else:
			print(len(v))


import sys
import bisect
input_ = lambda : sys.stdin.readline().strip('\r\n')
from math import log
sa = lambda : input_()
sb = lambda : int(input_())
sc = lambda : input_().split()
sd = lambda : list(map(int, input_().split()))
se = lambda : float(input_())
sf = lambda : list(input_())
flsh = lambda : sys.stdout.flush()
mod = 10 ** 9 + 7

def hnbhai():
	(n, k) = sd()
	a = sd()
	a.sort()
	if k == 0:
		print(n)
		return
	mx = max(a)
	x = 0
	for i in range(n):
		if x < a[i]:
			break
		else:
			x = a[i] + 1
	if x < mx:
		y = -(-(mx + x) // 2)
		if y in a:
			print(n)
			return
		print(n + 1)
	else:
		print(n + k)
for _ in range(sb()):
	hnbhai()


t = int(input())
for _ in range(t):
	(n, k) = tuple(map(int, input().split(' ')))
	S = list(set(list(map(int, input().split(' ')))))
	S.sort()
	elems = len(S)
	maxl = max(S)
	mexl = -1
	if k == 0:
		print(elems)
		continue
	for i in range(elems):
		if S[i] != i:
			mexl = i
			break
	if mexl == -1:
		print(elems + k)
	elif (maxl + mexl + 1) // 2 in S:
		print(elems)
	else:
		print(elems + 1)


n = int(input())
for i1 in range(n):
	seq = input()
	A1 = seq.split()
	length = int(A1[0])
	k = int(A1[1])
	seq = input()
	if k == 0:
		print(length)
		continue
	A2 = seq.split()
	A2 = [int(x) for x in A2]
	b = max(A2)
	if b == length - 1:
		print(length + k)
		continue
	count = 0
	for i2 in A2:
		if count not in A2:
			mex = count
			break
		count += 1
	S = round((mex + b) / 2 + 0.01)
	if S not in A2:
		print(length + 1)
	else:
		print(length)


import math

def maxAndMex(s, k):
	if k == 0:
		return len(s)
	if sum(s) == len(s) * (len(s) - 1) // 2:
		return k + len(s)
	i = 0
	while True:
		if i not in s:
			break
		i += 1
	if math.ceil((max(s) + i) / 2) in s:
		return len(s)
	else:
		return len(s) + 1
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = set(map(int, input().split()))
	print(maxAndMex(s, k))


from math import ceil
for t in range(int(input())):
	(n, k) = map(int, input().split())
	s = set([int(x) for x in input().split()])
	for num in range(n):
		if num not in s:
			mex = num
			break
	else:
		mex = n + 1
	if mex < n + 1:
		if k > 0:
			s.add(ceil((max(s) + mex) / 2))
		print(len(s))
	else:
		print(n + k)


import bisect
sr = lambda : input()
ir = lambda : int(sr())
lr = lambda : list(map(int, sr().split()))
inf = 10 ** 18
mod = 998244353
test = ir()
for t in range(test):
	(n, k) = lr()
	s = lr()
	if k == 0:
		print(len(s))
		continue
	s.sort()
	flg = True
	mex_s = 0
	max_s = max(s)
	for i in range(n):
		if i != s[i]:
			flg = False
			mex_s = i
			break
	if flg:
		print(len(s) + k)
	else:
		tmp = (max_s + mex_s + 1) // 2
		if s[bisect.bisect_left(s, tmp)] == tmp:
			print(len(s))
		else:
			print(len(s) + 1)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	nums = list(map(int, input().split()))
	if k == 0:
		print(n)
		continue
	mex = 0
	nums.sort()
	count = 0
	for i in nums:
		if i != count:
			mex = count
			break
		count += 1
	else:
		print(n + k)
		continue
	b = nums[-1]
	opt = (mex + b) // 2 if (mex + b) % 2 == 0 else (mex + b) // 2 + 1
	if opt in nums:
		print(n)
	else:
		print(n + 1)


from math import ceil
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = set(map(int, input().split()))
	answer = len(a)
	a_max = max(a)
	if len(a) < a_max + 1:
		a_mex = a_max + 1
		for i in range(a_max):
			if i not in a:
				a_mex = i
				break
		if ceil((a_mex + a_max) / 2) not in a and k != 0:
			answer += 1
	else:
		answer += k
	print(answer)


import sys

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

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

def main():
	for _ in range(int(input())):
		(n, k) = get_ints()
		ls = get_ls()
		st = set(ls)
		ax = max(ls)
		ex = 0
		for i in range(ax + 2):
			if i not in st:
				ex = i
				break
		if ex == ax + 1:
			print(n + k)
			continue
		if k > 0:
			st.add((ax + ex + 1) // 2)
		print(len(st))
main()


from os import path
import sys, time
from math import ceil, floor, gcd, log, log2, factorial, sqrt
from collections import defaultdict, Counter, OrderedDict, deque
from itertools import combinations, accumulate
from bisect import *
from functools import reduce
from operator import mul
star = lambda x: print(' '.join(map(str, x)))
grid = lambda r: [lint() for i in range(r)]
stpr = lambda x: sys.stdout.write(f'{x}' + '\n')
INF = float('inf')
if path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
import sys
from sys import stdin, stdout
from collections import *
from math import gcd, floor, ceil

def st():
	return list(stdin.readline().strip())

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

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

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

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

def pr(n):
	return stdout.write(str(n) + '\n')

def find_mex(arr, n):
	mex = -1
	for i in range(n):
		if arr[i] != i:
			return i
	return mex

def solve():
	(n, k) = invr()
	arr = inlt()
	arr.sort()
	res = 0
	missing_val = find_mex(arr, n)
	b = max(arr)
	if missing_val == -1 or k == 0:
		print(n + k)
	else:
		res = ceil((max(arr) + missing_val) / 2)
		arr.append(res)
		print(len(set(arr)))
t = 1
t = inp()
for _ in range(t):
	solve()


from sys import stdin, stdout

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

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

def read_int_tuple():
	return tuple(map(int, input().split()))

def read_int():
	return int(input())

def cdiv(x, y):
	return x // y if x % y == 0 else x // y + 1

def mex(A):
	sA = set(A)
	for i in range(0, max(A) + 10):
		if i not in sA:
			return i

def ans(K, S):
	S = set(S)
	a = mex(S)
	b = max(S)
	if a == b + 1:
		return len(S) + K
	if K > 0:
		S.add(cdiv(a + b, 2))
	return len(S)

def ans_slow(K, S):
	S = set(S)
	for _ in range(K):
		a = mex(S)
		b = max(S)
		S.add(cdiv(a + b, 2))
	return len(S)
for _ in range(read_int()):
	(_, K) = read_int_tuple()
	S = read_int_list()
	print(ans(K, S))


import sys
from math import ceil as c

def mex(s, max):
	res = 0
	for i in range(max):
		if i not in s:
			return i
for _ in range(int(input())):
	(n, k) = map(int, sys.stdin.readline().split())
	s = set(map(int, sys.stdin.readline().split()))
	m = max(s)
	if m == n - 1:
		print(n + k)
	else:
		for i in range(k):
			new = c((mex(s, m) + m) / 2)
			if new in s:
				break
			else:
				s.add(new)
		print(len(s))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	b = set(map(int, input().split()))
	a = 0
	while a in b:
		a += 1
	mx = max(b)
	if k == 0:
		print(len(b))
	elif a > mx:
		print(len(b) + k)
	else:
		b.add((a + mx + 1) // 2)
		print(len(b))


import math
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	a = set(map(int, input().split()))
	l = []
	for j in range(n):
		if j not in a:
			l.append(j)
	l.append(n + 1)
	if k == 0:
		print(n)
	elif l[0] != n + 1:
		x = math.ceil((l[0] + max(a)) / 2)
		ans = n
		if x not in a:
			ans = ans + 1
		print(ans)
	elif l[0] == n + 1:
		ans = n + k
		print(ans)


import math
a = [i for i in range(10 ** 5 + 10)]
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = list(map(int, input().split()))
	b = sorted(s)
	count = 0
	mex = max(b) + 1
	for i in range(n):
		if a[i] != b[i]:
			mex = a[i]
			break
	b = set(b)
	mx = max(b)
	if mex > mx:
		print(n + k)
	else:
		for i in range(k):
			c = math.ceil((mex + mx) / 2)
			if c not in b:
				b.add(c)
				mx = max(b)
			else:
				break
		print(len(b))


for y in range(int(input())):
	(n, m) = map(int, input().split())
	st = set(map(int, input().split()))
	mex = -1
	t = 0
	foo = 0
	lst = list(st)
	lst.sort()
	n = len(lst)
	for i in range(n):
		if i == lst[i]:
			pass
		else:
			mex = i
			foo = 1
			break
	ln = n
	if m == 0:
		print(n)
		continue
	if foo == 0:
		print(ln + m)
	else:
		res = mex + lst[-1]
		if res % 2 == 0:
			if res // 2 in lst:
				print(ln)
			else:
				print(ln + 1)
		elif res // 2 + 1 in lst:
			print(ln)
		else:
			print(ln + 1)


import math
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort()
	mex_val = 0
	max_val = l[-1]
	while True:
		if mex_val < n and l[mex_val] == mex_val:
			mex_val += 1
			continue
		else:
			new_val = math.ceil((mex_val + max_val) / 2)
			if k == 0 or new_val in l:
				print(n)
			elif mex_val > max_val:
				print(n + k)
			else:
				print(n + 1)
			break


import math
t = int(input())
for gg in range(t):
	(n, k) = list(map(int, input().split()))
	l = list(map(int, input().split()))
	m = max(l)
	z = set(l)
	m1 = len(z)
	if k == 0:
		print(m1)
	elif max(l) == n - 1 and n == m1:
		print(n + k)
	else:
		k1 = max(l)
		for i in range(0, k1 + 2):
			if i not in l:
				mex = i
				break
		s = math.ceil((mex + k1) / 2)
		if s not in l:
			print(m1 + 1)
		else:
			print(m1)


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10000000)

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

def read_index():
	return map(lambda x: int(x) - 1, input().split())

def read_list():
	return list(read_values())

def read_lists(N):
	return [read_list() for n in range(N)]

def solve():
	(N, K) = read_values()
	A = set(read_list())
	b = max(A)
	a = 0
	while a in A:
		a += 1
	for k in range(K):
		if a > b:
			return len(A) + K - k
		c = (a + b + 1) // 2
		if c in A:
			return len(A)
		A.add(c)
		while a in A:
			a += 1
	return len(A)

def main():
	T = int(input())
	res = []
	for _ in range(T):
		res.append(str(solve()))
	for r in res:
		print(r)
main()


import math

def mex(arr):
	i = 0
	while i in arr:
		i += 1
	return i
for _ in range(int(input())):
	(x, y) = list(map(int, input().split()))
	arr = set(map(int, input().split()))
	if mex(arr) > max(arr):
		print(x + y)
		continue
	elif y > 0:
		arr.add(math.ceil((mex(arr) + max(arr)) / 2))
	print(len(arr))


from sys import stdin, stdout
input = stdin.readline

def mex(arr):
	for i in range(0, 100000000):
		if i not in arr:
			return i

def ceil(a, b):
	return (a + b - 1) // 2
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	arr = [int(x) for x in input().split()]
	arr = sorted(arr)
	vals = [i for i in range(0, n)]
	if arr == vals:
		print(n + k)
		continue
	arr = set(arr)
	for i in range(min(k, 10)):
		val = ceil(mex(arr) + max(arr), 2)
		arr.add(val)
	print(len(arr))


for _ in range(int(input())):
	(n, k) = [int(x) for x in input().split(' ')]
	a = [int(x) for x in input().split(' ')]
	a.sort()
	if a[-1] == n - 1:
		print(n + k)
		continue
	mex = -1
	for i in range(n):
		if a[i] != i:
			mex = i
			break
	assert mex + 1
	newel = max(a) + mex
	if newel % 2:
		newel += 1
	newel = round(newel / 2)
	if a.count(newel):
		print(n)
	elif k:
		print(n + 1)
	else:
		print(n)


from math import ceil
t = int(input())
for j in range(t):
	(n, k) = map(int, input().split())
	(*a,) = map(int, input().split())
	a.sort()
	if k == 0:
		print(n)
	else:
		if a[0] != 0:
			x = 0
		else:
			x = 0
			for i in range(1, n):
				if a[i] - a[i - 1] > 1:
					x = a[i - 1] + 1
					break
			if x == 0:
				x = a[-1] + 1
		v = n
		if x == 0:
			if ceil((x + a[-1]) / 2) not in a:
				v += 1
		elif x == a[-1] + 1:
			v += k
		elif ceil((x + a[-1]) / 2) not in a:
			v += 1
		print(v)


import math

def check(lis):
	i = 0
	while True:
		if i not in lis:
			return i
		i += 1
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	lis = set(map(int, input().split()))
	mex = check(lis)
	if k == 0 or mex > max(lis):
		d = set(lis)
		print(len(d) + k)
	elif math.ceil((mex + max(lis)) / 2) in lis:
		print(n)
	else:
		print(n + 1)


import sys
max_int = 2147483648
min_int = -max_int
t = int(input())
for _t in range(t):
	(n, k) = map(int, sys.stdin.readline().split())
	a = set(map(int, sys.stdin.readline().split()))
	mex = 0
	mx = max(a)
	for i in range(k - 1, -1, -1):
		for j in range(mex, 10 ** 9 + 10):
			if j not in a:
				mex = j
				break
		if mex > mx:
			print(len(a) + i + 1)
			break
		to_add = (mx + mex + 1) // 2
		if to_add in a:
			print(len(a))
			break
		a.add(to_add)
	else:
		print(len(a))


for i in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	s = set(l)
	Max = max(l)
	Mex = 0
	while Mex in s:
		Mex += 1
	if Mex > Max or k == 0:
		print(n + k)
	else:
		s.add((Max + Mex + 1) // 2)
		print(len(s))


for i in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr.sort()
	if k == 0:
		print(n)
	elif arr[-1] == n - 1:
		print(n + k)
	else:
		mex = 0
		for i in range(len(arr)):
			if i != arr[i]:
				mex = i
				break
		mx = arr[-1]
		if int((mex + mx + 1) / 2) in arr:
			print(len(arr))
		else:
			print(len(arr) + 1)


import math

def mex(max, multiset):
	for i in range(max):
		if i not in multiset:
			return i
	return max + 1
for _ in range(int(input())):
	(num_elems, num_opers) = map(int, input().split())
	multi_set = set(map(int, input().split()))
	length = len(multi_set)
	if num_opers == 0:
		print(length)
		continue
	max_elem = max(multi_set)
	mex_elem = mex(max_elem, multi_set)
	a = math.ceil((max_elem + mex_elem) / 2)
	if a > max_elem:
		print(length + num_opers)
	elif a == max_elem:
		print(length)
	else:
		if a not in multi_set:
			length += 1
		print(length)


from bisect import bisect_left

def solve(arr, k):
	n = len(arr)
	if k == 0:
		return n
	arr.sort()
	l = 0
	while l < n and arr[l] == l:
		l += 1
	if l == n:
		return n + k
	m = (arr[-1] + l + 1) // 2
	i = bisect_left(arr, m)
	return n if i < n and arr[i] == m else n + 1
for _ in range(int(input())):
	(_, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	print(solve(arr, k))


from math import ceil
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	ar = list(set(map(int, input().split())))
	mex = 0
	ar.sort()
	maxx = ar[-1]
	n = len(ar)
	for i in range(n):
		if i != ar[i]:
			mex = i
			break
	else:
		mex = maxx + 1
	if k == 0:
		print(n)
	elif mex == maxx + 1:
		print(n + k)
	else:
		ele = ceil((mex + maxx) / 2)
		ar.append(ele)
		ar = set(ar)
		print(len(ar))


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

def sol():
	(n, k) = putin()
	A = set(putin())
	mx = max(A)
	mex = -1
	cnt = 0
	while True:
		if cnt not in A:
			mex = cnt
			break
		cnt += 1
	if mex == mx + 1:
		print(len(A) + k)
	else:
		new_elem = mex + mx + 1
		new_elem //= 2
		if new_elem in A or k == 0:
			print(len(A))
		else:
			print(len(A) + 1)
for iter in range(int(input())):
	sol()


import math
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	li = list(map(int, input().split()))
	s = set(li)
	mx = max(li)
	mex = 0
	for i in range(mx + 2):
		if i not in s:
			mex = i
			break
	if mex == mx + 1:
		print(n + k)
		continue
	if k > 0:
		s.add((mx + mex + 1) // 2)
	print(len(s))


from math import ceil

def solve():
	(n, k) = [int(x) for x in input().split()]
	A = [int(x) for x in input().split()]
	if k == 0:
		print(n)
		return
	mx = max(A)
	sA = set(A)
	mex = 0
	while mex in sA:
		mex += 1
	j = k
	spre = -1
	while j > 0:
		if mex > mx:
			print(mx + j + 1)
			return
		else:
			s = ceil((mex + mx) / 2)
			if s == spre:
				print(len(sA))
				return
			else:
				spre = s
				if s > mx:
					mx = s
				sA.add(s)
				while mex in sA:
					mex += 1
		j -= 1
	print(len(sA))
	return
t = int(input())
for i in range(0, t):
	solve()


import math

def mex(items):
	i = 0
	while i in items:
		i += 1
	return i

def main():
	t = int(input())
	for _ in range(t):
		(n, k) = list(map(int, input().split()))
		multiset = list(map(int, input().split()))
		num_set = set(multiset)
		mex_val = mex(num_set)
		max_val = max(num_set)
		if k != 0 and mex_val < max_val:
			val = math.ceil((max_val + mex_val) / 2)
			multiset.append(val)
			print(len(set(multiset)))
		else:
			print(len(set(multiset)) + k)
main()


from sys import stdin, stdout
(input, print) = (stdin.readline, stdout.write)

def main():
	for _ in range(int(input())):
		(n, k) = list(map(int, input().split()))
		a = list(map(int, input().split()))
		a.sort()
		i = 0
		while i < n and i == a[i]:
			i += 1
		if n == i:
			print(str(n + k) + '\n')
		elif (i + 1 + a[-1]) // 2 in a or k == 0:
			print(str(n) + '\n')
		else:
			print(str(n + 1) + '\n')
main()


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = set(map(int, input().split()))
	ma = max(s)
	i = 0
	while True:
		if i not in s:
			break
		i = i + 1
	if i == ma + 1:
		print(len(s) + k)
	else:
		if k:
			s.add((ma + i + 1) // 2)
		print(len(s))


import math
import sys, os.path
from collections import *
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
for _ in range(int(input())):
	d = defaultdict(int)
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	mex = 0
	count = 1
	d[a[0]] = 1
	for i in range(1, n):
		d[a[i]] = 1
		if a[i] != a[i - 1]:
			count += 1
	maxs = a[-1]
	for i in range(maxs + 2):
		if d[i] == 0:
			mex = i
			break
	temp = math.ceil((mex + maxs) / 2)
	if k != 0:
		if mex > maxs:
			print(count + k)
		elif d[temp] == 1:
			print(count)
		else:
			print(count + 1)
	else:
		print(count)


from math import ceil
import sys
finput = input
T = int(input())
frange = range
flen = len
fint = int
fmap = map
fprint = print
for i in frange(T):
	(n, k) = map(int, input().split())
	lis = list(map(int, input().split()))
	s = dict()
	for i in range(n):
		s[lis[i]] = 1
	Max = max(lis)
	min = 0
	for i in range(Max + 2):
		if i not in s:
			min = i
			break
	if min == Max + 1:
		print(n + k)
		continue
	if k > 0:
		s[(Max + min + 1) // 2] = 1
	print(len(s))


import math

def give_me_meh(a):
	for i in range(0, len(a)):
		if a[i] != i:
			return i
	return len(a)
for j in range(0, int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	max_ = max(a)
	mex = give_me_meh(a)
	if k == 0:
		print(len(a))
		continue
	if mex == len(a):
		print(len(a) + k)
	elif math.ceil((mex + max_) / 2) in a:
		print(len(a))
	else:
		print(len(a) + 1)


for _ in range(int(input())):
	a = list(map(int, input().split()))
	s = list(map(int, input().split()))
	s = sorted(s)
	mex = 0
	minim = s[0]
	if a[1] == 0:
		print(a[0])
	else:
		if s[0] == 0 and s[a[0] - 1] == a[0] - 1:
			print(a[0] + a[1])
			continue
		if mex < minim:
			if round((mex + s[a[0] - 1] + 0.5) / 2) in s:
				print(a[0])
			else:
				print(a[0] + 1)
			continue
		else:
			for i in range(a[0]):
				if i == 0:
					continue
				elif s[i] == minim + 1:
					minim = s[i]
				else:
					break
			mex = minim + 1
			if round((mex + s[a[0] - 1] + 0.5) / 2) in s:
				print(a[0])
			else:
				print(a[0] + 1)


def div(p, a):
	if p % a:
		return p // a + 1
	else:
		return p // a
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	li = list(map(int, input().split()))
	li.sort()
	dist = 1
	mn = 0
	mx = li[n - 1]
	for i in range(1, n):
		if li[i] != li[i - 1]:
			dist += 1
	for i in li:
		if i == mn:
			mn = i + 1
		elif i > mn:
			break
	if k == 0:
		ans = dist
	elif mn > mx:
		ans = dist + k
	else:
		x = div(mn + mx, 2)
		if x in li:
			ans = dist
		else:
			ans = dist + 1
	print(ans)


def search_mex(mex):
	for element in S_set:
		if element > mex:
			break
		elif element == mex:
			mex += 1
	return mex
for t in range(int(input())):
	(n, k) = map(int, input().split())
	S_set = list(set([int(i) for i in input().split()]))
	mex = 0
	a = search_mex(mex)
	b = S_set[-1]
	add = (a + b) // 2 + 1 if (a + b) % 2 else (a + b) // 2
	if add in S_set or k == 0:
		print(len(S_set))
	else:
		S_set.append(add)
		if add == max(S_set[-2:]):
			print(len(S_set) + k - 1)
		else:
			print(len(S_set))


import math
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	if k == 0:
		print(len(set(a)))
	elif a[0] == 0 and a[-1] == n - 1:
		print(len(set(a)) + k)
	elif a[-1] == n:
		print(len(set(a)))
	else:
		for i in range(0, n + 1):
			if i not in a:
				cnt = math.ceil((max(a) + i) / 2)
				a.append(cnt)
				print(len(set(a)))
				break


R = lambda : map(int, input().split())
(t,) = R()
exec(t * 'n,k=R();a=sorted(R());M=a[-1];m=min(i for i,x in enumerate(a+[n+1])if i<x);print((n+(k>0and m+M+1>>1not in a),n+k)[m>M]);')


from sys import stdin, stdout, setrecursionlimit
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush, nlargest
from math import *
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm, accumulate
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
import copy
import time
setrecursionlimit(10 ** 9)
starttime = time.time()
mod = int(pow(10, 9) + 7)
mod2 = 998244353

def data():
	return input()

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

def L():
	return list(sp())

def LF():
	return list(spf())

def sl():
	return list(ssp())

def sp():
	return map(int, data().split())

def spf():
	return map(int, input.readline().split())

def ssp():
	return map(str, data().split())

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

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

def pmat(A):
	for ele in A:
		print(*ele, end='\n')

def pmat2(A):
	for ele in A:
		for j in ele:
			print(j, end='')
		print()

def iseven(n):
	return n % 2 == 0

def seive(r):
	prime = [1 for i in range(r + 1)]
	prime[0] = 0
	prime[1] = 0
	for i in range(r + 1):
		if prime[i]:
			for j in range(2 * i, r + 1, i):
				prime[j] = 0
	return prime
for _ in range(int(input())):
	(n, k) = sp()
	a = L()
	mx = -1
	b = {i: 1 for i in range(n + 2)}
	for i in a:
		b[i] = 0
		if i > mx:
			mx = i
	for (i, v) in b.items():
		if v == 1:
			mex = i
			break
	ans = n
	t = ceil((mex + mx) / 2)
	if t != mex and k:
		if t not in a:
			ans += 1
	if mex - 1 == mx:
		ans += k
	print(ans)
endtime = time.time()


import math

def mex(nList):
	nList = set(nList)
	mex = 0
	while mex in nList:
		mex += 1
	return mex
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	x = mex(a)
	y = max(a)
	if k == 0:
		print(len(set(a)))
		continue
	if x < y:
		if math.ceil((x + y) / 2) in a:
			print(len(set(a)))
		else:
			print(len(set(a)) + 1)
	else:
		print(len(set(a)) + k)


import math
for ii in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	d = {}
	l = [0 for i in range(0, n)]
	maxx = -1
	for j in range(n):
		if a[j] < n:
			l[a[j]] = 1
		d[a[j]] = 1
		maxx = max(maxx, a[j])
	mex = -1
	for i in range(n):
		if l[i] == 0:
			mex = i
			break
	if mex == -1:
		mex = n + 1
	div = math.ceil((mex + maxx) / 2)
	if k == 0:
		print(n)
	elif mex > maxx:
		print(n + k)
	elif div in d:
		print(n)
	else:
		print(n + 1)


import math
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = list(map(int, input().split()))
	maxi = max(s)
	mexi = -1
	f = 0
	a = set(s)
	for i in range(maxi):
		if i not in a:
			mexi = i
			f = 1
			break
	if f == 0:
		mexi = maxi + 1
		print(n + k)
	else:
		ans = math.ceil((maxi + mexi) / 2)
		if ans in s or k == 0:
			print(n)
		else:
			print(n + 1)


from math import ceil
import sys
finput = input
T = int(input())
frange = range
flen = len
fint = int
fmap = map
fprint = print
for i in frange(T):
	(n, k) = fmap(fint, finput().split())
	arr = list(fmap(fint, finput().split()))
	fmax = max(arr)
	h = dict()
	t = 0
	for j in frange(n):
		h[arr[j]] = 1
	for i in range(fmax + 2):
		if i not in h:
			t = i
			break
	if fmax + 1 == t:
		fprint(len(h) + k)
	else:
		if k != 0:
			h[ceil((fmax + t) / 2)] = 1
		fprint(flen(h))


def mex(a):
	x = 0
	while x in a:
		x += 1
	return x
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	if k == 0:
		a = input()
		print(n)
	else:
		a = set([int(x) for x in input().split()])
		m = max(a)
		me = mex(a)
		if me > m:
			print(n + k)
		else:
			a.add((me + m + 1) // 2)
			print(len(a))