Given an array A consisting of N distinct integers (1 ≤ A_{i} ≤ 2 \cdot N), we have to perform K moves.
We perform the following steps in one move:

Select an integer X such that 1 ≤ X ≤ 2 \cdot N and X \ne A_{i} for all i (X is not equal to any element of the current array).
Append X to A.
The *score* of this move = (\max_{1 ≤ i ≤ |A|} A_{i}) - X.  
Note that the *score* is calculated after appending X. Thus, X can be the maximum element of the array as well.

For e.g. if A = [3, 1, 5] and we append X = 2 to A, then, A becomes [3, 1, 5, 2] and the *score* of this move is \max([3, 1, 5, 2]) - 2 = 5 - 2 = 3.

Find the maximum sum of *scores* we can achieve after performing exactly K moves.

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

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of multiple lines of input.
- The first line of each test case contains three space-separated integers N and K — the size of the array A and the number of moves respectively.
- The second line of each test case contains N space-separated integers A_{1}, A_{2}, \dots, A_{N} denoting the array A.

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

For each test case, output the maximum sum of *scores* we can achieve after performing exactly K moves.  
It is guaranteed that it is always possible to perform K moves under the given constraints. 

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

$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 10^{5}$
$1 ≤K ≤N$
$1 ≤ A_{i} ≤ 2 \cdot N$
- All $A_{i}$ are distinct.
- Sum of $N$ over all test cases does not exceed $2 \cdot 10^{5}$.

----- Sample Input 1 ------ 
3
3 1
1 3 6
2 2
1 2
3 2
1 2 5

----- Sample Output 1 ------ 
4
1
3

----- explanation 1 ------ 
Test Case 1: We can perform the following move:
- Append $X = 2$. Score of this move $= \max([1, 3, 6, 2]) - 2 = 6 - 2 = 4$

Hence, the maximum total score is $4$.

Test Case 2: We can perform the following moves:
- Append $X = 4$. Score of this move $= \max([1, 2, 4]) - 4 = 4 - 4 = 0$
- Append $X = 3$. Score of this move $= \max([1, 2, 4, 3]) - 3 = 4 - 3 = 1$

Hence, the maximum total score is $0+1=1$.

Test Case 3: We can perform the following moves:
- Append $X = 4$. Score of this move $= \max([1, 2, 5, 4]) - 4 = 5 - 4 = 1$
- Append $X = 3$. Score of this move $= \max([1, 2, 5, 4, 3]) - 3 = 5 - 3 = 2$

Hence the maximum total score is $1+2=3$.

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Mathematics


Solutions:
t = int(input())
for i in range(t):
	(n, k) = input().split()
	n = int(n)
	k = int(k)
	A = [int(x) for x in input().split()]
	B = []
	m = max(A)
	M = 2 * n
	count = 0
	if min(A) != 1:
		count = 1
		B.append(1)
		A.append(1)
		n += 1
	sum1 = 0
	sum2 = 0
	A.sort()
	for j in range(n - 1):
		d = A[j + 1] - A[j]
		if A[j + 1] - A[j] > 1:
			for l in range(d - 1):
				B.append(A[j] + 1 + l)
				count += 1
				if count == k:
					break
					break
		if count == k:
			break
	if count < k:
		for j in range(k - count):
			B.append(m + 1 + j)
	for j in range(k):
		sum1 += m - B[j]
		sum2 += M - B[j]
	sum2 -= M - B[k - 1]
	print(max(sum1, sum2))


for _ in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	assert len(a) == n
	a.sort()
	sum_holes = 0
	sum_holes_2 = -1
	last_elt = 0
	k_left = k - 1
	for i in range(len(a)):
		elt = a[i]
		holes = min(k_left, elt - last_elt - 1)
		sum_holes += last_elt * holes + holes * (holes + 1) // 2
		k_left -= holes
		if k_left == 0:
			if holes < elt - last_elt - 1:
				sum_holes_2 = sum_holes + (last_elt + holes + 1)
			else:
				j = i
				while j < n - 1 and a[j + 1] == a[j] + 1:
					j += 1
				if j != n - 1:
					sum_holes_2 = sum_holes + (a[j] + 1)
				else:
					sum_holes_2 = -1
			break
		last_elt = elt
	if a[-1] == 2 * n:
		sum_holes = -1
	else:
		sum_holes += a[-1] * k_left + k_left * (k_left + 1) // 2
	if sum_holes != -1:
		sum_holes = (k - 1) * (2 * n) - sum_holes
	if sum_holes_2 != -1:
		sum_holes_2 = k * a[-1] - sum_holes_2
	print(max(sum_holes, sum_holes_2))


import numpy as np
testcase = int(input())
for _ in range(testcase):
	score = 0
	(N, K) = map(lambda x: int(x), input().split(' '))
	A = set(map(lambda x: int(x), input().split(' ')))
	maxval = N * 2
	full_list = {i + 1 for i in range(N * 2)}
	missing_values = sorted(list(A ^ full_list))
	print(max([(K - 1) * maxval - sum(missing_values[0:K - 1]), K * max(A) - sum(missing_values[0:K])]))


def distinct_numbers(arr, N, K):
	cur = [0 for _ in range(2 * N + 1)]
	missing = []
	for val in arr:
		cur[val] = 1
	for i in range(1, 2 * N + 1):
		if cur[i] == 0:
			missing.append(i)
	max_val = max(arr)
	first = 2 * N * (K - 1) - sum(missing[:K - 1])
	second = max_val * K - sum(missing[:K])
	print(max(first, second))
T = int(input())
for _ in range(T):
	(N, K) = tuple(map(int, input().split()))
	arr = list(map(int, input().split()))
	distinct_numbers(arr, N, K)


def calc(start, times):
	(i, ans) = (start, 0)
	while times != 0:
		if i not in st:
			ans += mx - i
			times -= 1
		i += 1
	return ans
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	(mx, st) = (max(arr), set(arr))
	if mx == 2 * n:
		print(calc(1, k))
	else:
		mx = 2 * n
		ans1 = calc(1, k - 1)
		(i, ans2) = (1, 0)
		mx = max(arr)
		while k != 0:
			if i not in st:
				if i < mx:
					ans2 += mx - i
					k -= 1
				elif i == mx + 1:
					mx = 2 * n
					k -= 1
					ans2 += calc(mx + 2, k)
					break
			i += 1
		print(max(ans1, ans2))


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	cur = [0 for _ in range(2 * n + 1)]
	missing = []
	for val in arr:
		cur[val] = 1
	for i in range(1, 2 * n + 1):
		if cur[i] == 0:
			missing.append(i)
	first = 2 * n * (k - 1) - sum(missing[:k - 1])
	second = max(arr) * k - sum(missing[:k])
	print(max(first, second))


for i in range(int(input())):
	(n, k) = map(int, input().split())
	array = list(map(int, input().split()))
	mar = [0] * (2 * n + 1)
	b = []
	for ele in array:
		mar[ele] = 1
	for i in range(1, 2 * n + 1):
		if mar[i] == 0:
			b.append(i)
	mxm = max(array)
	an = int(-10 ** 13)
	an = max(an, (k - 1) * (2 * n) - sum(b[0:k - 1]))
	an = max(an, k * mxm - sum(b[0:k]))
	print(an)


h = int(input())
for _ in range(h):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	m = n * 2
	mx = max(l)
	ansa = 0
	ansb = 0
	f = [0] * (m + 1)
	for i in range(n):
		f[l[i]] = 1
	for i in range(1, 2 * n):
		if f[i] == 1:
			continue
		else:
			ansa += mx - i
			if k != 1:
				ansb += 2 * n - i
				k -= 1
			else:
				break
	print(max(ansa, ansb))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	mark = [0] * (2 * n + 1)
	b = []
	for elem in arr:
		mark[elem] = 1
	for i in range(1, 2 * n + 1):
		if mark[i] == 0:
			b.append(i)
	mx = max(arr)
	ans = int(-10 ** 13)
	ans = max(ans, (k - 1) * (2 * n) - sum(b[0:k - 1]))
	ans = max(ans, k * mx - sum(b[0:k]))
	print(ans)


numInp = lambda : int(input())
lstImp = lambda : list(map(int, input().split()))
strImp = lambda : input()
spacedStrImp = lambda : list(input())
seperateImp = lambda : map(int, input().split())
for i in range(int(input())):
	(lenOfLst, numOfMoves) = seperateImp()
	lst = lstImp()
	limit = lenOfLst * 2
	maxValue = max(lst)
	possibleElements = [0] * (limit + 1)
	possibleOutput1 = 0
	possibleOutput2 = 0
	for i in lst:
		possibleElements[i] += 1
	for i in range(1, limit):
		if possibleElements[i] != 1:
			possibleOutput1 += maxValue - i
			if numOfMoves == 1:
				break
			else:
				possibleOutput2 += limit - i
				numOfMoves -= 1
	print(max(possibleOutput1, possibleOutput2))


from functools import reduce
T = int(input())
for _ in range(T):
	(N, K) = map(int, input().split(' '))
	A = list(map(int, input().split(' ')))

	def solve():
		max_a = reduce(max, A)
		elms = set(A)
		ap1 = 0
		ap2 = 0
		moves = 0
		idx = 0
		while moves < K:
			idx += 1
			if idx in elms:
				continue
			if K - moves > 1:
				ap1 += 2 * N - idx
			ap2 += max_a - idx
			moves += 1
		return max(ap1, ap2)
	print(solve())


def solve():
	(N, K) = map(int, input().split())
	numbers = sorted(list(map(int, input().split())))
	sumOfAbsent = 0
	lastAbsent = 0
	lastNumber = 0
	oldK = K
	for number in numbers:
		if number - lastNumber - 1 < K:
			K -= number - lastNumber - 1
			sumOfAbsent += int((lastNumber + 1 + number - 1) / 2 * (number - lastNumber - 1))
			lastNumber = number
		else:
			sumOfAbsent += int((lastNumber + 1 + lastNumber + K) / 2 * K)
			lastAbsent = lastNumber + K
			K = 0
			break
	if K > 0:
		sumOfAbsent += int(K * (lastNumber + 1 + lastNumber + K) / 2)
		lastAbsent = lastNumber + K
	optionOne = numbers[-1] * oldK - sumOfAbsent
	optionTwo = 2 * N * (oldK - 1) - (sumOfAbsent - lastAbsent)
	print(max(optionOne, optionTwo))
for i in range(int(input())):
	solve()


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = [int(i) for i in input().split()]
	c = a
	d = k
	t = {}
	for i in a:
		t[i] = i
	i = 1
	ans1 = 0
	maxi1 = max(a)
	while k != 0:
		if i in t:
			i += 1
		else:
			a.append(i)
			ans1 += maxi1 - i
			k -= 1
			i += 1
	j = 1
	t[2 * n] = 2 * n
	maxi2 = 2 * n
	d -= 1
	ans2 = 0
	while d != 0:
		if j in t:
			j += 1
		else:
			ans2 += maxi2 - j
			d -= 1
			j += 1
	print(max(ans1, ans2))


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	mark = [0] * (2 * n + 1)
	a = []
	for x in arr:
		mark[x] = 1
	for i in range(1, 2 * n + 1):
		if mark[i] == 0:
			a.append(i)
	m = max(arr)
	ans = int(-10 ** 13)
	ans = max(ans, (k - 1) * (2 * n) - sum(a[0:k - 1]))
	ans = max(ans, k * m - sum(a[0:k]))
	print(ans)


def mgc(arr, k, n):
	set_arr = set(arr)
	missing = []
	for i in range(1, 2 * n + 1):
		if i not in set_arr:
			missing.append(i)
	(ans1, ans2) = (2 * n * (k - 1) - sum(missing[:k - 1]), max(arr) * k - sum(missing[:k]))
	return max(ans1, ans2)
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	print(mgc(arr, k, n))


import sys
input = sys.stdin.readline

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

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

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

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

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

def outlt(lst):
	sys.stdout.write(' '.join(map(str, lst)) + '\n')

def outplt(lst):
	sys.stdout.write('\n'.join(map(str, lst)))
ans = []
for _ in range(inp()):
	(N, K) = inlt()
	A = invr()
	N2 = N * 2
	X = []
	Ac = set(A)
	mx = max(Ac)
	for x in range(1, N2 + 1):
		if x in Ac:
			continue
		X.append(x)
	for i in range(K):
		if X[i] > mx:
			break
	else:
		i += 1
	a1 = mx * i - sum(X[:i])
	a2 = N2 * (K - 1) - sum(X[:K - 1])
	ans.append(max(a1, a2))
outplt(ans)


import sys
input = sys.stdin.readline

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

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

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

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

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

def outlt(lst):
	sys.stdout.write(' '.join(map(str, lst)) + '\n')

def outplt(lst):
	sys.stdout.write('\n'.join(map(str, lst)))
ans = []
for _ in range(inp()):
	(N, K) = inlt()
	A = set(invr())
	(mx, N2) = (max(A), N * 2)
	X = sorted(set(list(range(1, N2 + 1))) - A)
	(an1, an2) = (0, 0)
	for k in range(K - 1):
		if mx > X[k]:
			an1 += mx - X[k]
		an2 += N2 - X[k]
	if mx > X[K - 1]:
		an1 += mx - X[K - 1]
	ans.append(max(an1, an2))
outplt(ans)


for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	a = set(map(int, input().split()))
	m = sorted(set(range(1, 1 + 2 * n)) - a)
	strategy1 = max(a) * k - sum(m[:k])
	strategy2 = 2 * n * (k - 1) - sum(m[:k - 1])
	print(max(strategy1, strategy2))


T = int(input())
for i in range(T):
	(N, K) = map(int, input().split())
	A = list(map(int, input().split()))
	max_A = max(A)
	not_A = [0] * (2 * N + 1)
	b = []
	for i in A:
		not_A[i] = 1
	for i in range(1, len(not_A)):
		if not_A[i] == 0:
			b.append(i)
	s1 = K * max_A - sum(b[:K])
	s2 = (K - 1) * 2 * N - sum(b[:K - 1])
	if s1 > s2:
		print(s1)
	else:
		print(s2)


for _ in range(int(input())):
	(N, K) = map(int, input().split())
	A = list(map(int, input().split()))
	b = []
	a = [0] * (N * 2 + 1)
	for i in A:
		a[i] = i
	for i in range(1, N * 2 + 1):
		if a[i] == 0:
			b.append(i)
	l = K * max(A) - sum(b[:K])
	li = (K - 1) * 2 * N - sum(b[:K - 1])
	if l > li:
		print(l)
	else:
		print(li)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	nl = list(map(int, input().split()))
	M = max(nl)
	L = []
	m = [0] * (2 * n + 1)
	for j in nl:
		m[j] = 1
	for j in range(1, 2 * n + 1):
		if m[j] == 0:
			L.append(j)
	p = k * M - sum(L[:k])
	q = (k - 1) * 2 * n - sum(L[:k - 1])
	print(max(p, q))


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = [0] * (n * 2 + 1)
	c = []
	for i in a:
		b[i] = 1
	for i in range(1, n * 2 + 1):
		if b[i] == 0:
			c.append(i)
	s1 = k * max(a) - sum(c[:k])
	s2 = (k - 1) * 2 * n - sum(c[:k - 1])
	if s1 > s2:
		print(s1)
	else:
		print(s2)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	z = max(a)
	not_a = []
	d = [0] * (2 * n + 1)
	for j in a:
		d[j] = 1
	for j in range(1, 2 * n + 1):
		if d[j] == 0:
			not_a.append(j)
	p = k * z - sum(not_a[:k])
	q = (k - 1) * 2 * n - sum(not_a[:k - 1])
	print(max(p, q))


for i in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = a[:]
	m = [0] * (n * 2 + 1)
	for i in a:
		m[i] = 1
	l = []
	for i in range(1, 2 * n + 1):
		if m[i] == 0:
			l.append(i)
	max_a = max(a)
	t1 = k * max_a - sum(l[:k])
	t2 = (k - 1) * 2 * n - sum(l[:k - 1])
	print(max(t1, t2))


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	list1 = list(map(int, input().split()))
	li = [0] * (n * 2 + 1)
	new = []
	for i in list1:
		li[i] = 1
	for i in range(1, n * 2 + 1):
		if li[i] == 0:
			new.append(i)
	l = k * max(list1) - sum(new[:k])
	l1 = (k - 1) * 2 * n - sum(new[:k - 1])
	if l > l1:
		print(l)
	else:
		print(l1)


for t in range(int(input())):
	(N, K) = map(int, input().split())
	A = list(map(int, input().split()))
	C = 2 * N
	(B, D) = ([0] * (C + 1), [])
	for i in A:
		B[i] = 1
	for i in range(1, C + 1):
		if B[i] == 0:
			D.append(i)
	S1 = max(A) * K - sum(D[:K])
	S2 = (K - 1) * C - sum(D[:K - 1])
	print(max(S1, S2))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	maxElem = max(l)
	notL = []
	m = [0] * (2 * n + 1)
	for i in l:
		m[i] = 1
	for i in range(1, 2 * n + 1):
		if m[i] == 0:
			notL.append(i)
	s1 = k * maxElem - sum(notL[:k])
	s2 = (k - 1) * 2 * n - sum(notL[:k - 1])
	print(max(s1, s2))


from collections import Counter
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	l = list(map(int, input().split()))
	l1 = Counter(l)
	l2 = []
	res = max(l)
	tot = 0
	tot1 = 0
	for i in range(1, 2 * n + 1):
		if l1[i] == 0:
			l2.append(i)
	for i in range(m):
		if res > l2[i]:
			tot += res - l2[i]
		if i < m - 1:
			tot1 += 2 * n - l2[i]
	print(max(tot, tot1))


from collections import Counter
t = int(input())
for _ in range(t):
	(a, b) = map(int, input().split())
	l = list(map(int, input().split()))
	z = Counter(l)
	l1 = []
	for i in range(1, 2 * a + 1):
		if z[i] == 0:
			l1.append(i)
	j = k = 0
	h = max(l)
	for i in range(b):
		if h > l1[i]:
			j += h - l1[i]
		if i < b - 1:
			k += 2 * a - l1[i]
	print(max(j, k))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	temp = 1
	arr.sort()
	ans = 0
	x = k
	for i in range(n):
		while k > 0:
			if temp < arr[i]:
				ans += temp
				temp += 1
				k -= 1
			else:
				break
		if k == 0:
			break
		temp = arr[i] + 1
	while k > 0:
		if temp <= 2 * n:
			ans += temp
			temp += 1
			k -= 1
		else:
			break
	temp -= 1
	print(max(max(arr) * x - ans, 2 * n * (x - 1) - ans + temp))


for i in range(int(input())):
	(n, k) = map(int, input().split())
	l = [int(x) for x in input().split()]
	a = list(set((int(x) for x in range(1, 2 * n + 1))) - set(l))
	a.sort()
	print(max(-1, (k - 1) * (2 * n) - sum(a[:k - 1]), k * max(l) - sum(a[:k])))


for i in range(int(input())):
	(n, k) = map(int, input().split())
	l = [int(x) for x in input().split()]
	sl = set(l)
	a = [int(x) for x in range(1, 2 * n + 1)]
	sa = set(a)
	a = list(sa - sl)
	a.sort()
	m = max(l)
	b = -1
	b = max(b, (k - 1) * (2 * n) - sum(a[:k - 1]))
	b = max(b, k * m - sum(a[:k]))
	print(b)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	li = list(map(int, input().split()))
	a = set(li)
	b = [i for i in range(1, 2 * n + 1)]
	b = set(b)
	a = b.difference(a)
	a = list(a)
	a.sort()
	c = 0
	c1 = 0
	x = max(li)
	for i in range(k):
		if i < k:
			c += x - a[i]
		if i < k - 1:
			c1 += abs(2 * n - a[i])
	print(max(c, c1))


for _ in range(int(input())):
	(N, K) = map(int, input().split())
	A = list(map(int, input().split()))
	A.sort()
	all = set(list(range(1, 2 * N + 1)))
	rem = list(all - set(A))
	rem.sort()
	met1 = (K - 1) * 2 * N - sum(rem[:K - 1])
	met2 = K * A[-1] - sum(rem[:K]) if len(rem) >= K else 0
	print(max(met1, met2))


t = int(input())
for _ in range(t):
	(x, y) = map(int, input().split())
	ma = x * 2
	lis = list(map(int, input().split()))
	dic = [0 for i in range(ma + 1)]
	lis_max = 0
	for i in lis:
		dic[i] = 1
		lis_max = max(i, lis_max)
	cnt = 0
	ind = 1
	ans = 0
	while cnt < y:
		if dic[ind] == 0:
			ans += lis_max - ind
			cnt += 1
		ind += 1
	ans1 = 0
	if lis_max != ma:
		cnt = 0
		ind = 1
		y -= 1
		dic[ma] = 1
		while cnt < y:
			if dic[ind] == 0:
				ans1 += ma - ind
				cnt += 1
			ind += 1
	ans = max(ans, ans1)
	print(ans)


from collections import Counter
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = Counter(a)
	m = max(a)
	c = []
	for i in range(1, 2 * n + 1):
		if b[i] == 0:
			c.append(i)
	total1 = 0
	total2 = 0
	for i in range(k):
		if m > c[i]:
			total1 += m - c[i]
		if i < k - 1:
			total2 += 2 * n - c[i]
	print(max(total1, total2))


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	l = [0 for _ in range(2 * n + 1)]
	maxelem = 0
	for ae in a:
		l[ae] = 1
		if ae > maxelem:
			maxelem = ae
	score1 = 0
	k1 = k
	i = 1
	while i < 2 * n + 1 and k1 > 0:
		if l[i] == 0:
			if i > maxelem:
				maxelem = i
			score1 += maxelem - i
			k1 -= 1
		i += 1
	score2 = 0
	if l[-1] == 0:
		maxelem = 2 * n
		k2 = k - 1
		i = 1
		while i < 2 * n + 1 and k2 > 0:
			if l[i] == 0:
				score2 += maxelem - i
				k2 -= 1
			i += 1
	print(max(score1, score2))


mapInput = lambda : map(int, input().split())
listInput = lambda : list(mapInput())
for _ in range(int(input())):
	(n, k) = mapInput()
	a = listInput()
	rem = list(set(list(range(1, 2 * n + 1))) - set(a))
	rem.sort()
	print(max((k - 1) * 2 * n - sum(rem[:k - 1]), k * max(a) - sum(rem[:k])))


mapInput = lambda : map(int, input().split())
listInput = lambda : list(mapInput())
for _ in range(int(input())):
	(n, k) = mapInput()
	a = listInput()
	all = set(list(range(1, 2 * n + 1)))
	rem = list(all - set(a))
	rem.sort()
	ansOne = (k - 1) * 2 * n - sum(rem[:k - 1])
	ansTwo = k * max(a) - sum(rem[:k]) if len(rem) >= k else 0
	print(max(ansTwo, ansOne))


def calc1(a, k):
	m = max(a)
	n = len(a)
	s = set(a)
	ans = 0
	for i in range(1, 2 * n + 1):
		if k == 0 or i in s:
			continue
		ans += m - i
		s |= {i}
		k -= 1
	return ans

def calc(a, k):
	return max(calc1(a + [2 * n], k - 1), calc1(a, k))
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	print(calc(a, k))


from collections import Counter
for t in range(int(input())):
	(n, k) = map(int, input().split())
	a = list((int(i) for i in input().split()))
	d = Counter(a)
	b = []
	for i in range(1, 2 * n + 1):
		if d[i] == 0:
			b.append(i)
	v1 = 0
	v2 = 0
	mx = max(a)
	for i in range(k):
		v1 += mx - b[i]
	if d[2 * n] == 0:
		for i in range(k - 1):
			v2 += 2 * n - b[i]
	print(max(v1, v2))


tc = int(input())
while tc > 0:
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	m = max(l)
	t1 = [0] * (n * 2 + 1)
	t2 = [0] * (n * 2 + 1)
	for i in l:
		t1[i] = 1
		t2[i] = 1
	sum1 = 0
	sum2 = 0
	(q1, q2) = (k, k)
	(m1, m2) = (2 * n, m)
	t1[2 * n] = 1
	q1 -= 1
	for i in range(1, n * 2 + 1):
		if q1 == 0 and q2 == 0:
			break
		if q1 != 0 and t1[i] == 0:
			t1[i] = 1
			sum1 += m1 - i
			q1 -= 1
		if q2 != 0 and t2[i] == 0:
			if m2 < i:
				m2 = i
			t2[i] = 1
			sum2 += m2 - i
			q2 -= 1
	print(max(sum1, sum2))
	tc -= 1


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	flag = [False] * (2 * n + 1)
	for item in arr:
		flag[item] = True
	temp = []
	for i in range(1, 2 * n + 1):
		if flag[i] == False:
			temp.append(i)
	max_ = max(arr)
	res = max(2 * n * (k - 1) - sum(temp[0:k - 1]), k * max_ - sum(temp[0:k]))
	print(res)


from bisect import bisect_left, bisect_right
import math
from collections import defaultdict
from bisect import bisect_left
from heapq import heapify, heappush, heappop
from collections import deque
import sys
from math import gcd, sqrt, log10, log2, floor, ceil, sqrt
from collections import deque, defaultdict
input = sys.stdin.readline

def il():
	return [int(a) for a in input().strip().split()]

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

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

def ot(in_p, *args, e=' '):
	if type(in_p) == list:
		print(*in_p, end=e)
	if type(in_p) == str or type(in_p) == int:
		print(in_p, end=e)
		for l in args:
			print(l, end=e)
	print()

def a_pwr_n(a, n, mod):
	if n == 1:
		return a % mod
	if n % 2 == 0:
		val = a_pwr_n(a, n // 2, mod)
		return val % mod * val % mod
	else:
		return a % mod * a_pwr_n(a, n - 1, mod) % mod

def rg(*ag):
	if len(ag) == 3:
		return range(ag[0], ag[1], ag[2])
	elif len(ag) == 2:
		return range(ag[0], ag[1])
	elif len(ag) == 1:
		return range(ag[0])
	else:
		raise 'invalid input'

def ispal(i, j, st):
	while i <= j:
		if st[i] == st[j]:
			i = i + 1
			j = j - 1
		else:
			return False
	return True
mod = 1000000000 + 7
dx = [-1, -2, 1, 2, 2, -2, -1, 1]
dy = [2, 1, 2, 1, -1, -1, -2, -2]
for _ in range(ii()):
	(n, k) = il()
	a = il()
	sa = set(a)
	s = [i for i in range(1, 2 * n + 1) if i not in sa]
	z = max(a)
	an = 0
	p = sorted(s)
	if p[k - 1] < z:
		print(max(k * z - sum(p[:k]), max(s) * (k - 1) - sum(p[:k - 1])))
	else:
		print(max(s) * (k - 1) - sum(p[:k - 1]))


a = int(input())
for i in range(a):
	(N, K) = map(int, input().split())
	A = list(map(int, input().split()))
	A.sort()
	B = [0] * (2 * N + 1)
	for j in range(N):
		B[A[j]] = 1
	x = 0
	y = 0
	z = 0
	for j in range(1, 2 * N + 1):
		if B[j] == 0:
			y += 1
			x += j
			z = j
		if y == K:
			break
	p = (K - 1) * (2 * N) - (x - z)
	q = K * A[N - 1] - x
	if p >= q:
		print(p)
	else:
		print(q)


def max_score(numbers, k):
	missing = set(range(1, 2 * len(numbers) + 1)) - numbers
	max_missing = max(missing)
	return max(max_score_adding_mins(numbers | {max_missing}, missing - {max_missing}, k - 1), max_score_adding_mins(numbers, missing, k))

def max_score_adding_mins(numbers, missing, k):
	if k == 0:
		return 0
	missing_mins = list(sorted(missing))
	max_present = max(numbers)
	score = 0
	for i in range(k):
		score += max_present - missing_mins[i]
	return score
for _ in range(int(input())):
	(_, k) = map(int, input().split())
	numbers = set((int(x) for x in input().split()))
	r = max_score(numbers, k)
	print(r)


for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	a = set(map(int, input().split()))
	m = sorted(set(range(1, 1 + 2 * n)) - a)
	maks = max(a)
	s1 = maks * k - sum(m[:k])
	s2 = 2 * n * (k - 1) - sum(m[:k - 1])
	print(max(s1, s2))


T = int(input())
for t in range(T):
	(N, K) = map(int, input().split())
	B = list(range(1, 2 * N + 1))
	A = list(map(int, input().split()))
	for i in range(N):
		B[A[i] - 1] = 0
	(tot, tot2) = (0, 0)
	Kidx = 1
	idx = 0
	mx = max(A)
	while Kidx <= K:
		if B[idx] > 0:
			tot += max(mx - B[idx], 0)
			if Kidx <= K - 1:
				tot2 += 2 * N - B[idx]
			Kidx += 1
		idx += 1
	print(max(tot, tot2))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	mark = [0] * (2 * n + 1)
	b = []
	for x in a:
		mark[x] = 1
	for i in range(1, 2 * n + 1):
		if mark[i] == 0:
			b.append(i)
	mx = max(a)
	ans = 0
	ans = max(ans, (k - 1) * (2 * n) - sum(b[0:k - 1]))
	ans = max(ans, k * mx - sum(b[0:k]))
	print(ans)


t = int(input())
while t != 0:
	(n, k) = map(int, input().split())
	ls = list(map(int, input().split()))
	m = {}
	mx = 0
	for e in ls:
		mx = max(mx, e)
		m[e] = 1
	arr = []
	(ans1, ans2, c) = (0, 0, 0)
	for i in range(1, 2 * n + 1):
		if i in m.keys():
			continue
		mx = max(mx, i)
		if c < k - 1:
			ans2 += abs(2 * n - i)
		if c < k:
			ans1 += abs(mx - i)
			c += 1
	print(max(ans1, ans2))
	t -= 1


t = int(input())
for T in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	count = [0 for i in range(2 * n + 1)]
	for i in range(n):
		count[a[i]] = 1
	maxm = max(a)
	ans1 = ans2 = 0
	temp = k
	for i in range(1, 2 * n + 1):
		if count[i] == 0:
			if i > maxm:
				maxm = i
			ans1 += maxm - i
			temp -= 1
		if temp == 0:
			break
	k -= 1
	for i in range(1, 2 * n + 1):
		if count[i] == 0 and k != 0:
			ans2 += 2 * n - i
			k -= 1
	print(max(ans1, ans2))


for _ in range(int(input())):
	(N, K) = map(int, input().split())
	A = list(map(int, input().split()))
	d = {}
	mx1 = 0
	for n in A:
		mx1 = max(mx1, n)
		d[n] = 1
	mx2 = 2 * N
	k = 0
	(res1, res2) = (0, 0)
	for i in range(1, 2 * N + 1):
		if i not in d:
			res1 += mx1 - i
			if k < K - 1:
				res2 += mx2 - i
			k += 1
			if k == K:
				break
	print(max(res1, res2))


import bisect
import math
import sys
from collections import Counter, deque
for _ in range(int(sys.stdin.readline())):
	(n, k) = map(int, sys.stdin.readline().split())
	a = [int(i) for i in sys.stdin.readline().split()]
	mark = [0] * (2 * n + 1)
	b = []
	for x in a:
		mark[x] = 1
	for i in range(1, 2 * n + 1):
		if mark[i] == 0:
			b.append(i)
	mx = max(a)
	ans = int(-10 ** 13)
	ans = max(ans, (k - 1) * (2 * n) - sum(b[0:k - 1]))
	ans = max(ans, k * mx - sum(b[0:k]))
	print(ans)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	nums = list(map(int, input().split()))
	maxNum = max(nums)
	s = set(nums)
	ans1 = 0
	(i, j) = (0, 1)
	while j <= 2 * n and i < k:
		if j not in s:
			s.add(j)
			maxNum = max(j, maxNum)
			ans1 += maxNum - j
			i += 1
		j += 1
	s = set(nums)
	s.add(2 * n)
	maxNum = 2 * n
	ans2 = 0
	(i, j) = (1, 1)
	while j <= 2 * n and i < k:
		if j not in s:
			s.add(j)
			maxNum = max(j, maxNum)
			ans2 += maxNum - j
			i += 1
		j += 1
	print(max(ans1, ans2))