Read problems statements in Mandarin and Russian. Translations in Vietnamese to be uploaded soon. 
There is new delicious item in Chef's menu - a doughnut chain. Doughnuts connected successively in line forming a chain.

Chain of 3 doughnuts

Chef has received an urgent order for making a chain of N doughnuts. He noticed that there are exactly N cooked doughnuts in the kitchen, some of which are already connected in chains. The only thing he needs to do is connect them in one chain.
He can cut one doughnut (from any position in a chain) into two halves and then use this cut doughnut to link two different chains.

Help Chef determine the minimum number of cuts needed to complete the order.

------ Input ------ 

The first line of the input contains an integer T denoting the number of test cases.
The first line of each test case contains two integer N and M denoting the size of order and number of cooked chains respectively.
The second line contains M space-separated integers A_{1}, A_{2}, ..., A_{M} denoting the size of the chains.

It is guaranteed that N is equal to the sum of all A_{i}'s over 1≤i≤M.

------ Output ------ 

For each test case, output a single line containing an integer corresponding to the number of cuts needed Chef to make the order.
------ 
------ Constraints -----

$1 ≤ T ≤ 200$
$1 ≤ N ≤ 2*10^{9}$
$1 ≤ A_{i} ≤ 10^{5}$

Subtask 1: 10 points

$1 ≤ M ≤ 2*10^{4}$
$A_{i} = 1$

Subtask 2: 30 points

$1 ≤ M ≤ 100$

Subtask 3: 60 points

$1 ≤ M ≤ 2*10^{4}$

----- Sample Input 1 ------ 
2
11 3
4 3 4
6 3
3 2 1
----- Sample Output 1 ------ 
2
1
----- explanation 1 ------ 
Example 1: We could cut 2 doughnut from any "chain" and use them to connect chains to the one.  For example, let's cut it from the first chain. After this we will have chains of sizes 2, 3, 4 and two doughnuts that have been cut. So we could connect the first chain with second and second with third using these two doughnuts.
Example 2: We cut doughnut from the last "chain" and connect the first two chains.

Image for second example. Yellow doughnut has been cut.

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Sorting

Greedy algorithms


Solutions:
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	l = list(map(int, input().split()))
	if len(l) == 1:
		print(0)
		continue
	l.sort(reverse=True)
	l1 = []
	j = 0
	l1.append(l.pop())
	cnt = 0
	while j < len(l) - 1:
		if l1[0] > 0:
			l1[0] -= 1
			j += 1
			cnt += 1
		elif l1[0] == 0:
			l1.pop()
			if j < len(l) - 2:
				l1.append(l.pop())
			else:
				cnt += 1
				j += 1
	if len(l1) > 0 and l1[0] > 0:
		cnt += 1
	print(cnt)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	noofcuts = 0
	l = [int(x) for x in input().split()]
	l = sorted(l)
	while l[0] < m - 1:
		m -= 1
		m -= l[0]
		noofcuts += l[0]
		del l[0]
	if l[0] == m - 2:
		noofcuts += m - 2
	elif l[0] > m - 2:
		noofcuts += m - 1
	print(noofcuts)


def solve():
	lst.sort()
	count = 0
	i = 0
	j = m - 1
	while i < j:
		if lst[i] > 0:
			j = j - 1
			count += 1
			lst[i] = lst[i] - 1
		else:
			i = i + 1
	print(count)
t = int(input())
for _ in range(t):
	(n, m) = list(map(int, input().split()))
	lst = list(map(int, input().split()))
	solve()


ans = 0
for i in range(int(input())):
	(n, m) = map(int, input().split())
	a = [int(j) for j in input().split()]
	a = sorted(a)
	t = m - 1
	k = 0
	while k < t:
		while a[k] > 0 and k < t:
			ans = ans + 1
			a[k] = a[k] - 1
			t = t - 1
		k = k + 1
	print(ans)
	ans = 0


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	(l1, l2) = ([], [])
	for i in range(m):
		if a[i] == 1:
			l1.append(a[i])
		else:
			l2.append(a[i])
	(ans, temp) = (0, False)
	if len(l1) == m:
		print(m // 2)
		temp = True
	a.sort()
	s = 0
	c = 0
	p1 = m - 1
	while p1 >= 0:
		s += a[p1]
		c += 1
		p1 -= 1
		if s >= n - (c - 1) and c != 0:
			break
	if temp == False:
		print(c - 1)


for _ in range(int(input())):
	(n, m) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	arr.sort()
	ans = 0
	(i, j) = (0, m - 1)
	while i < j:
		while i < j and arr[i] > 0:
			ans += 1
			j -= 1
			arr[i] -= 1
		i += 1
	print(ans)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	donuts = sorted([int(x) for x in input().split()])
	links = m - 1
	end = len(donuts) - 1
	for i in range(len(donuts)):
		if i >= end or donuts[i] >= links:
			break
		else:
			d = donuts[i]
			if i >= end - d:
				break
			else:
				links -= 1
				donuts[end - d] = d + sum(donuts[end - d:end + 1])
				end -= d
	print(links)


def minCuts(n, A):
	A = sorted(A, reverse=True)
	currentLength = A[0]
	i = 1
	while currentLength < n:
		currentLength += A[i] + 1
		A[-1] -= 1
		if A[-1] == 0:
			del A[-1]
		i += 1
	return i - 1
assert minCuts(11, [4, 3, 4]) == 2
assert minCuts(6, [3, 2, 1]) == 1
tc = int(input())
while tc > 0:
	(n, m) = [int(x) for x in input().split()]
	chain = [int(x) for x in input().split()]
	result = minCuts(n, chain)
	print(result)
	tc -= 1


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr.sort()
	s = 0
	c = 0
	p1 = m - 1
	while p1 >= 0:
		if s + arr[p1] <= n:
			c += 1
			s += arr[p1]
			p1 -= 1
		else:
			p1 -= 1
		if s >= n - (c - 1) and c != 0:
			break
	print(c - 1)


T = int(input())
for t in range(T):
	(N, M) = map(int, input().split())
	A = [int(a) for a in input().split()]
	A.sort()
	c = 0
	i = 0
	j = M - 2
	while i <= j:
		if A[i] > 0:
			A[i] -= 1
			A[j] += A[j + 1]
			c += 1
			j -= 1
		else:
			i += 1
	print(c)


import sys

def solve(y):
	y = sorted(y)
	i = 0
	j = len(y) - 1
	resp = 0
	while i < j:
		y[j - 1] += y[j] + 1
		j -= 1
		if y[i] == 1:
			i += 1
		else:
			y[i] -= 1
		resp += 1
	return resp
casos = int(input())
for k in range(casos):
	line = input()
	x = line.split()
	n = x[0]
	m = x[1]
	line = input()
	y = [int(x) for x in line.split()]
	print(solve(y))


from sys import stdin, stdout
import math
from itertools import permutations, combinations
from collections import defaultdict

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

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

def I():
	return int(stdin.readline())
P = 1000000007

def main():
	try:
		for _ in range(I()):
			(t, n) = In()
			a = L()
			a.sort()
			s = 0
			c = 0
			for i in range(n):
				s += a[i] + 1
				if s >= n:
					c = i
					break
			print(n - c - 1)
	except:
		pass
main()


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	s = 0
	c = 0
	for i in range(m):
		s += a[i] + 1
		if s >= m:
			c = i
			break
	print(m - c - 1)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	v = list(map(int, input().split()))
	v.sort()
	ans = 0
	for i in range(m):
		temp = m - (i + 1)
		ans += v[i]
		if ans >= temp - 1:
			if ans == temp - 1:
				print(temp - 1)
			else:
				print(temp)
			break


for t in range(int(input())):
	(N, M) = [int(x) for x in input().split()]
	l = [int(x) for x in input().split()]
	l.sort()
	i = 0
	s = 0
	while s + l[i] <= M - i - 2:
		s += l[i]
		i += 1
	print(M - i - 1)


import sys

def ans():
	for _ in range(int(sys.stdin.readline())):
		(n, m) = map(int, sys.stdin.readline().split())
		a_m = list(map(int, sys.stdin.readline().split()))
		d = {}
		for i in a_m:
			d[i] = True
		a_m.sort()
		a_m.reverse()
		chain = a_m[0]
		i = 1
		b = m - 1
		cuts = 0
		if n in d:
			chain = n
			cuts = 0
		elif a_m[0] > n:
			cuts = 1
		while chain < n and i < m:
			chain += a_m[i]
			if chain < n:
				chain += 1
				a_m[b] -= 1
				if a_m[b] == 0:
					b -= 1
			cuts += 1
			i += 1
		yield cuts
for i in ans():
	print(i)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	d = 0
	m -= 1
	for i in range(m + 1):
		d += a[i]
		if d >= m - i - 1:
			if d == m - i - 1:
				print(m - i - 1)
			else:
				print(m - i)
			break


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	mli = list(map(int, input().split()))
	mli.sort()
	count = 0
	while len(mli) > 1:
		mli[0] -= 1
		if mli[0] == 0:
			mli.pop(0)
		mli.pop()
		count += 1
	print(count)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr.sort()
	l = len(arr)
	current = 0
	count = 0
	while current < l - 1:
		arr[current] -= 1
		p = arr.pop()
		l -= 1
		arr[-1] += p + 1
		count += 1
		if arr[current] == 0:
			current += 1
	print(count)


t = int(input())
for __ in range(t):
	(n, m) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	a.sort()
	i = 0
	ans = 0
	while True:
		if m == 1:
			break
		if a[i] + 2 <= m:
			m -= a[i] + 1
			ans += a[i]
			i += 1
		else:
			ans += m - 1
			m = 1
	print(ans)


__author__ = 'Om Kumar Sahoo'
cas = int(input())
for t in range(cas):
	(n, m) = [int(x) for x in input().split()]
	arr = input().split()
	count1 = 0
	for i in range(m):
		arr[i] = int(arr[i])
	arr = sorted(arr)
	rsum = 0
	for i in range(int(m + 1 / 2)):
		rsum += arr[i]
		if rsum >= m - i - 1:
			break
	print(m - i - 1)


out = []
t = int(input())
for i in range(t):
	(n, m) = [int(j) for j in input().split()]
	l = [int(j) for j in input().split()]
	l.sort()
	c = 0
	d = 0
	for i in l:
		c += i
		d += 1
		if c > m - 1 - d:
			d -= 1
			break
		if c == m - 1 - d:
			break
	out.append(m - 1 - d)
for i in out:
	print(i)


for _ in range(int(input())):
	(n, m) = [int(i) for i in input().split()]
	a = [int(i) for i in input().split()]
	count = 0
	a.sort()
	while len(a) > 1:
		a[0] -= 1
		if a[0] == 0:
			a.pop(0)
		a.pop(len(a) - 1)
		count += 1
	print(count)


for i in range(int(input())):
	(n, m) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort(reverse=True)
	c = 0
	j = m - 1
	for i in range(m - 1):
		if l[i + 1] != 0:
			c += 1
			l[j] -= 1
			if l[j] == 0:
				j -= 1
	print(c)


t = int(input())
while t > 0:
	x = input().split(' ')
	n = int(x[0])
	m = int(x[1])
	count = 0
	a = []
	y = input().split(' ')
	for i in range(m):
		a.append(int(y[i]))
	q = m - 1
	s = 0
	a.sort()
	for i in range(m):
		if a[i] < q:
			s = s + a[i]
			q = q - a[i] - 1
	if q > 0:
		s = s + q
	print(s)
	t = t - 1


for T in range(int(input())):
	(N, M) = map(int, input().split())
	A = list(map(int, input().split()))
	A.sort()
	Rem = M - 1
	Ans = 0
	if M == 1:
		print(0)
		continue
	for Ai in A:
		v = Ai + 1
		if Rem - v == 0:
			Ans += Ai
			break
		elif Rem - v > 0:
			Rem -= v
			Ans += Ai
		else:
			Ans += Rem
			Rem = 0
			break
	print(Ans)


def solve():
	(n, m) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	arr.sort()
	s = 0
	k = m
	i = 0
	while k > 1:
		arr[i] -= 1
		s += 1
		if arr[i] == 0:
			i += 1
			k -= 1
		k -= 1
	print(s)
t = int(input())
for _ in range(t):
	solve()


for _ in range(int(input())):
	(N, M) = input().split()
	N = int(N)
	M = int(M)
	a = []
	count = 0
	a = list(map(int, input().split()))
	lun = len(a)
	a.sort()
	while len(a) > 1:
		a[0] -= 1
		if a[0] == 0:
			a.pop(0)
		a.pop(len(a) - 1)
		count += 1
	print(count)


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	c = 0
	x = 0
	y = m - 2
	while x <= y:
		if a[x] > 0:
			a[x] -= 1
			a[y] += a[y + 1]
			c += 1
			y -= 1
		else:
			x += 1
	print(c)


t = int(input())
for case in range(t):
	(n, m) = list(map(int, input().split()))
	d = list(map(int, input().split()))
	if n == m:
		print(m // 2)
	else:
		d = sorted(d)
		count = 0
		target = m
		for i in d:
			if i >= target:
				count += target - 1
				target = 0
			else:
				count += i
				target = target - i - 1
			if target <= 0:
				break
		print(count)


def soln(n, m, arr):
	arr.sort()
	res = 0
	low = 0
	high = m - 2
	while low <= high:
		res += min(arr[low], high - low + 1)
		high -= arr[low]
		low += 1
	return res
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	arr = list(map(int, input().split()))
	print(soln(n, m, arr))


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split(' '))
	a = list(map(int, input().split(' ')))
	a.sort()
	c = 0
	for i in range(m):
		if m - i - 1 > c:
			if m - i - 2 > c + a[i]:
				c += a[i]
			elif m - i - 2 == c + a[i]:
				c += a[i]
				break
			else:
				c = m - i - 1
		else:
			break
	print(c)


t = int(input())
for i in range(t):
	(n, m) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	d = a + [m - 1]
	d.sort()
	if d[0] == m - 1:
		print(m - 1)
	else:
		d.remove(m - 1)
		c = 0
		while len(d) > 2:
			if d[0] == 1:
				d.pop(0)
			else:
				d[0] -= 1
			d[-2] = d[-1] + d[-2] + 1
			d.pop()
			c += 1
		if len(d) == 1:
			print(c)
		else:
			print(c + 1)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	chains = [int(s) for s in input().split()]
	chains.sort()
	req = m - 1
	idx = 0
	cut = 0
	while req > 0:
		if chains[idx] > req:
			cut = cut + req
			req = 0
		else:
			req = req - 1
			req = req - chains[idx]
			cut = cut + chains[idx]
			idx = idx + 1
	print(cut)


for _ in range(int(input())):
	(N, M) = list(map(int, input().split()))
	A = list(map(int, input().split()))
	A.sort()
	M -= 1
	Doughnuts = 0
	for i in range(len(A)):
		if M == 0:
			break
		if M >= A[i]:
			Doughnuts += A[i]
			M = max(0, M - A[i] - 1)
		else:
			Doughnuts += M
			M = 0
	print(Doughnuts)


for tests in range(int(input())):
	[N, M] = [int(i) for i in input().split()]
	A = [int(i) for i in input().split()]
	A.sort()
	A.reverse()
	s = A[0]
	i = 1
	if s >= N:
		print(0)
	else:
		while s < N:
			s += A[i] + 1
			A[-1] -= 1
			if A[-1] == 0:
				A.pop()
			i += 1
		print(i - 1)


t = int(input())
while t > 0:
	nm = input().split()
	n = int(nm[0])
	m = int(nm[1])
	a = input().split()
	for i in range(m):
		a[i] = int(a[i])
	i = 0
	j = m - 1
	x = 0
	a = sorted(a)
	while i < j:
		a[i] -= 1
		a[j] += 1
		x += 1
		if a[i] == 0:
			i += 1
		j -= 1
	print(x)
	t -= 1


for _ in range(int(input())):
	(n, m) = map(int, input().split(' '))
	A = list(map(int, input().split(' ')))
	A.sort()
	count = 0
	i = 0
	while True:
		mini = A[i]
		i += 1
		if mini < m:
			count += mini
			m = m - 1 - mini
		else:
			count += m - 1
			m = 1
		if m < 2:
			break
	print(count)


def solve():
	(n, m) = map(int, input().split())
	lis = sorted(list(map(int, input().split())))
	ans = int()
	(low, high) = (0, m - 2)
	while low <= high:
		if lis[low] > 0:
			lis[low] -= 1
			lis[high] += lis[high + 1]
			high -= 1
			ans += 1
		else:
			low += 1
	print(ans)
for _ in range(int(input())):
	solve()


for _ in range(int(input())):
	(n, m) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	a.sort()
	c = 0
	while m - 1 > 0:
		y = a[0]
		if y <= m - 2:
			a.pop(0)
			m -= 1
			m -= y
			c += y
		elif y > m - 2:
			y = m - 1
			a[0] = y - m + 1
			m -= y
			c += y
	print(c)


def count_cuts(chains):
	big_index = len(chains) - 1
	small_index = 0
	cuts = 0
	while big_index > small_index:
		if chains[small_index] == 0:
			small_index += 1
			continue
		else:
			chains[small_index] = chains[small_index] - 1
		cuts += 1
		big_index -= 1
	return cuts
t = int(input())
for case in range(t):
	(N, M) = list(map(int, input().split()))
	chains = sorted(list(map(int, input().split())))
	print(count_cuts(chains))


for _ in range(int(input())):
	z = input().split()
	(n, m) = map(int, z[:2])
	z = input().split()
	ds = list(map(int, z[:m]))
	lnks = m - 1
	ds.sort()
	while lnks > 0:
		if ds[0] <= lnks:
			lnks -= ds.pop(0) + 1
		else:
			ds[0] -= lnks
			lnks = 0
	print(n - sum(ds))


n_tests = int(input())
for i in range(n_tests):
	(n, m) = [int(x) for x in input().split()]
	array = [int(x) for x in input().split()]
	array1 = array
	array.sort()
	gaps = len(array) - 1
	j = gaps
	i = result = 0
	if gaps < array[0]:
		print(gaps)
		continue
	else:
		while j > i:
			a = array[i]
			i += 1
			c = j
			j -= a
			if j < i:
				result += c - i + 1
				break
			result += a
	print(result)


for t in range(int(input())):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	count = 0
	numoflnk = m - 1
	nthdon = 0
	while numoflnk > 0:
		if a[nthdon] < numoflnk:
			numoflnk -= a[nthdon] + 1
			count += a[nthdon]
			nthdon += 1
			continue
		numoflnk -= 1
		count += 1
	print(count)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	vals = list(map(int, input().split()))
	vals.sort()
	gaps = m - 1
	cuts = 0
	while vals[0] < gaps:
		cuts += vals[0]
		gaps = gaps - (vals[0] + 1)
		vals.pop(0)
	print(cuts + gaps)


import collections
import math
T = int(input())
for t in range(T):
	[N, M] = map(int, input().split())
	A = map(int, input().split())
	freq = dict(collections.Counter(A))
	cuts = 0
	m = M
	for k in sorted(freq.keys()):
		p = freq[k]
		i = min(p, math.floor((m - 1) / (k + 1)))
		m = m - i * (k + 1)
		cuts += i * k
		if i != p:
			break
	cuts = cuts + m - 1
	print(cuts)


tc = int(input())
while tc:
	flag = 0
	(n, m) = input().split(' ')
	n = int(n)
	m = int(m)
	a = []
	x = str(input())
	a = list(x.split(' '))
	a = [int(i) for i in a]
	a.sort()
	required_split = m - 1
	split_count = 0
	for i in range(m):
		if required_split <= 0:
			break
		elif a[i] <= required_split:
			required_split -= a[i] + 1
			split_count += a[i]
		elif a[i] > required_split:
			split_count += required_split
			required_split = 0
	if a[len(a) - 1] == 1:
		split_count = int(m / 2)
	print(split_count)
	tc -= 1


for _ in range(int(input())):
	(n, m) = map(int, input().strip().split())
	a = list(map(int, input().split()))
	a = sorted(a)
	total = 0
	ans = 0
	for i in range(m):
		k = m - i - total - 1
		if k <= a[i]:
			ans = total + k
			break
		total += a[i]
	print(ans)


t = int(input())
i = 0
while i < t:
	(n, m) = map(int, input().split())
	holes = []
	a = [int(x) for x in input().split()]
	no_of_holes = m - 1
	a.sort()
	k = 0
	ans = 0
	for j in a:
		if no_of_holes == 0:
			break
		if j <= no_of_holes - 1:
			no_of_holes -= j + 1
			ans += j
		elif j > no_of_holes - 1:
			ans += no_of_holes
			no_of_holes = 0
	i += 1
	print(ans)


from sys import stdin, stdout
import math
from collections import Counter
import functools
import time
import bisect

def tr():
	return range(int(line()))

def sm():
	return map(int, line().split())

def ln():
	return list(sm())

def nl():
	return int(line())

def ssm():
	return map(str, line().split())

def line():
	return stdin.readline().rstrip()

def b(x):
	return bin(x).replace('0b', '')

def o(x):
	if type(x) != type(''):
		x = str(x)
	stdout.write(x + '\n')

def osp(x):
	if type(x) != type(''):
		x = str(x)
	stdout.write(x + ' ')

def ol(x):
	stdout.write(' '.join(map(str, x)))

def wline():
	return stdin.read().split()

def main():
	for _ in tr():
		(n, m) = sm()
		cooked_donuts = ln()
		cooked_donuts.sort()
		s = 0
		index = 0
		for i in range(m):
			s += cooked_donuts[i] + 1
			if s >= m:
				index = i
				break
		print(m - index - 1)
main()


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	chains = list(map(int, input().split()))
	chains.sort()
	d = 0
	cuts = m - 1
	for i in chains:
		if d < cuts:
			if i > cuts - d:
				d = cuts
				break
			if i <= cuts:
				cuts = cuts - 1
				d = d + i
		else:
			break
	print(d)


test = int(input())
while test != 0:
	test -= 1
	(n, m) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort()
	sum = 0
	i = 0
	j = len(l) - 1
	while i < j:
		if l[i] == 1:
			i += 1
			j = j - 1
		else:
			l[i] = l[i] - 1
			j = j - 1
		sum += 1
	print(sum)


a = int(input())
for i in range(a):
	(N, M) = map(int, input().split())
	A = list(map(int, input().split()))
	b = max(A)
	c = min(A)
	A.sort()
	m = M
	x = 0
	for j in range(M):
		if m <= 1:
			break
		elif A[j] >= m - 2:
			if A[j] == m - 2 or A[j] == m - 1:
				x = sum(A[:j + 1])
				break
			else:
				x = sum(A[:j]) + m - 1
				break
		else:
			m -= A[j] + 1
	print(x)


for _ in range(int(input())):
	(k, n) = map(int, input().split())
	lst = list(map(int, input().split()))
	cnt = 0
	x = 0
	lst.sort()
	while len(lst) > 2:
		while lst[0] != 0:
			if len(lst) == 2:
				break
			lst[-2] += lst[-1]
			del lst[-1]
			cnt += 1
			lst[0] -= 1
			if lst[0] == 0:
				del lst[0]
				break
	if lst[0] == 0:
		del lst[0]
	if len(lst) == 2:
		print(cnt + 1)
	else:
		print(cnt)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	l = map(int, input().split())
	l = list(l)
	l.sort()
	c = 0
	j = m - 1
	for i in range(len(l)):
		if l[i] < j:
			j = j - 1 - l[i]
			c = c + l[i]
		else:
			break
	ans = c + j
	print(ans)


import collections
case = int(input())
for _ in range(case):
	(n, m) = map(int, input().split(' '))
	arr = list(map(int, input().split(' ')))
	arr.sort()
	dq = collections.deque(arr)
	res = 0
	while len(dq) > 2:
		value = dq.popleft() - 1
		dq.append(dq.pop() + dq.pop())
		if value > 0:
			dq.appendleft(value)
		res += 1
	if len(dq) == 2:
		res += 1
	print(res)