There are one cat, $k$ mice, and one hole on a coordinate line. The cat is located at the point $0$, the hole is located at the point $n$. All mice are located between the cat and the hole: the $i$-th mouse is located at the point $x_i$ ($0 < x_i < n$). At each point, many mice can be located.

In one second, the following happens. First, exactly one mouse moves to the right by $1$. If the mouse reaches the hole, it hides (i.e. the mouse will not any more move to any point and will not be eaten by the cat). Then (after that the mouse has finished its move) the cat moves to the right by $1$. If at the new cat's position, some mice are located, the cat eats them (they will not be able to move after that). The actions are performed until any mouse hasn't been hidden or isn't eaten.

In other words, the first move is made by a mouse. If the mouse has reached the hole, it's saved. Then the cat makes a move. The cat eats the mice located at the pointed the cat has reached (if the cat has reached the hole, it eats nobody).

Each second, you can select a mouse that will make a move. What is the maximum number of mice that can reach the hole without being eaten?


-----Input-----

The first line contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Then $t$ test cases follow.

Each test case consists of two lines. The first line contains two integers $n$ and $k$ ($2 \le n \le 10^9$, $1 \le k \le 4 \cdot 10^5$). The second line contains $k$ integers $x_1, x_2, \dots x_k$ ($1 \le x_i < n$) — the initial coordinates of the mice.

It is guaranteed that the sum of all $k$ given in the input doesn't exceed $4 \cdot 10^5$.


-----Output-----

For each test case output on a separate line an integer $m$ ($m \ge 0$) — the maximum number of mice that can reach the hole without being eaten.


-----Examples-----

Input
3
10 6
8 7 5 4 9 4
2 8
1 1 1 1 1 1 1 1
12 11
1 2 3 4 5 6 7 8 9 10 11
Output
3
1
4


-----Note-----

None

Difficulty: EASY
Tags: Sorting

Greedy algorithms
Skill types: Sorting

Greedy algorithms

Starter code:

Solutions:
for _ in range(int(input())):
	(n, _) = map(int, input().split())
	(length, count) = (0, 0)
	for x in sorted(map(int, input().split()), reverse=True):
		if length < x:
			length = length + n - x
			count = count + 1
		else:
			break
	print(count)


from bisect import bisect_right
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = sorted(list(map(int, input().split())))
	c = 0
	ans = 0
	p = []
	for i in a[::-1]:
		if c < i:
			ans += 1
		else:
			break
		c += n - i
	print(ans)


def mices_saved(n, k, mices):
	mices.sort()
	cat = 0
	pos = len(mices) - 1
	result = 0
	while pos > -1 and cat < mices[pos]:
		cat += n - mices[pos]
		pos -= 1
		result += 1
	return result
test_cases = int(input())
for i in range(test_cases):
	(n, k) = list(map(int, input().split()))
	mices = list(map(int, input().split()))
	print(mices_saved(n, k, mices))


def solve():
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr = sorted(arr)
	cat = 0
	ans = 0
	for i in range(k - 1, -1, -1):
		x = arr[i]
		if x <= cat:
			break
		dis = n - x
		cat += dis
		ans += 1
	print(ans)
t = int(input())
for i in range(t):
	solve()


res = []
for i in range(int(input())):
	(n, k) = map(int, input().split())
	a = sorted(list(map(int, input().split())), reverse=True)
	cat = 0
	cnt = 0
	for i in a:
		if i <= cat:
			break
		cat += n - i
		cnt += 1
	res.append(cnt)
print(*res, sep='\n')


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	mice = list(map(int, input().split()))
	mice.sort()
	cat = 0
	flag = 0
	for j in range(k - 1, -1, -1):
		cat = cat + n - mice[j]
		if cat > n - 1:
			cat = cat - (n - mice[j])
			flag = 1
			break
	if flag == 0:
		print(k)
	else:
		print(max(k - (j + 1), 1))


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	x = sorted(map(int, input().split()))
	cat = ans = 0
	for i in x[::-1]:
		if cat >= i:
			break
		cat += n - i
		ans += 1
	print(ans)


def solve(mice, n, k):
	mice = sorted(mice)
	cat = 0
	saved = 0
	end = k - 1
	while cat < n and end >= 0:
		mx = mice[end]
		move = n - mx
		if cat < mx:
			saved += 1
		cat += move
		end -= 1
	print(saved)
t = int(input())
while t:
	(n, k) = map(int, input().split())
	mice = list(map(int, input().split()))
	solve(mice, n, k)
	t -= 1


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	lst = sorted(map(int, input().split()), reverse=True)
	cat = 0
	temp = 0
	for i in lst:
		if i <= cat:
			break
		temp += 1
		cat += n - i
	print(temp)


def save():
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	l = len(a)
	c = 0
	for i in range(l - 1, 0, -1):
		c += n - a[i]
		if a[i - 1] - c <= 0:
			k -= i
			break
	return k
t = int(input())
res = ''
while t > 0:
	t -= 1
	res += f'{save()}\n'
print(res)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	x = list(map(int, input().split()))
	x.sort()
	x = x[::-1]
	now = 0
	cnt = 0
	for g in x:
		if now >= g:
			break
		cnt += 1
		now += n - g
	print(cnt)


import sys
input = sys.stdin.readline
for tc in range(int(input())):
	(n, k) = map(int, input().split())
	a = sorted(map(int, input().split()))
	(sm, cnt) = (0, 0)
	for i in a[::-1]:
		if i <= sm:
			break
		cnt += 1
		sm += n - i
	print(cnt)


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


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	x = sorted(list(map(int, input().split())))
	hole = 0
	c = 0
	for i in x[::-1]:
		if i <= c:
			break
		hole += 1
		c += n - i
	print(hole)


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


for s in range(int(input())):
	sum = 0
	flag = 0
	(n, k) = [int(i) for i in input().split()]
	mice = [int(i) for i in input().split()]
	mice.sort(reverse=True)
	for i in range(k):
		sum += n - mice[i]
		if sum >= n:
			flag = 1
			print(i)
			break
	if flag == 0:
		print(k)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	lst = list(map(int, input().split()))
	lst.sort(reverse=True)
	c = 0
	cnt = 0
	for i in lst:
		if c < i:
			cnt += 1
			c += n - i
		else:
			break
	print(cnt)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort(reverse=True)
	i = 0
	count = 0
	for j in l:
		if i < j:
			count += 1
			i += n - j
		else:
			break
	print(count)


def main():
	(n, k) = map(int, input().split())
	x = list(map(int, input().split()))
	x.sort(reverse=True)
	ans = 0
	c_i = 0
	i = 0
	while c_i < n and i < k:
		if x[i] > c_i:
			ans += 1
			c_i += n - x[i]
			i += 1
		else:
			break
	print(ans)
t = int(input())
while t > 0:
	t -= 1
	main()


for t in range(int(input())):
	(n, k) = map(int, input().split())
	lst = sorted(list(map(int, input().split())))[::-1]
	r = k
	summ = 0
	for i in range(k):
		summ += n - lst[i]
		if summ >= n:
			r = i
			break
	print(r)


import sys

def mgc(n, k, arr):
	cat = 0
	while arr:
		temp = arr.pop()
		if cat < temp:
			cat += n - temp
		else:
			return k - len(arr) - 1
	return k
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = sorted(list(map(int, input().split())))
	print(mgc(n, k, arr))


nTests = int(input())
for tests in range(0, nTests):
	nk = list(map(int, input().split()))
	n = nk[0]
	k = nk[1]
	mice = list(map(int, input().split()))
	mice.sort(reverse=True)
	saved = 0
	dist = n
	for closest in mice:
		dist -= n - closest
		if dist <= 0:
			break
		else:
			saved += 1
	print(saved)


t = int(input())
for i in range(t):
	(n, k) = [int(i) for i in input().split()]
	x = [int(i) for i in input().split()]
	mouse = 0
	ans = 0
	x.sort(reverse=True)
	for j in x:
		if mouse >= j:
			break
		ans += 1
		mouse += n - j
	print(ans)


def save_more_mice(n, mice):
	mice.sort()
	mice_saved = 0
	cat = 0
	while len(mice) > 0:
		mouse = mice.pop()
		if mouse <= cat:
			break
		steps_to_hole = n - mouse
		mice_saved += 1
		cat += steps_to_hole
	return mice_saved
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split(' '))
	mice = list(map(int, input().split(' ')))
	print(save_more_mice(n, mice))


n = int(input())
for i in range(n):
	(n, k) = list(map(int, input().split()))
	b = list(map(int, input().split()))
	b = sorted(b, reverse=True)
	s = 0
	n1 = n
	for j in b:
		if n1 - (n - j) > 0:
			n1 -= n - j
			s += 1
		else:
			break
	print(s)


t = int(input())
for j in range(0, t):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort(reverse=True)
	c = 0
	f = 0
	for i in range(0, k):
		if l[i] > c:
			c += n - l[i]
			f += 1
		else:
			break
	print(f)


T = int(input().strip())
for t in range(T):
	(hole, mice) = map(int, input().split())
	M = list(map(int, input().split()))
	M.sort(reverse=True)
	cat = 0
	saved = 0
	for m in M:
		dist = hole - m
		if dist < hole - cat:
			saved += 1
			cat += dist
		else:
			break
	print(saved)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	L = [*map(int, input().split())]
	L.sort(reverse=True)
	ans = 0
	cat = 0
	for el in L:
		step = n - el
		if cat >= el:
			break
		ans += 1
		cat += step
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr.sort(reverse=True)
	sumy = 0
	count = 0
	for i in arr:
		if sumy < i:
			sumy += n - i
			count += 1
		if sumy > i:
			break
	print(count)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	x = list(map(int, input().split()))
	x.sort()
	s = n - x[k - 1]
	i = k - 1
	while i >= 0 and s <= n - 1:
		i -= 1
		s += n - x[i]
	print(k - 1 - i)


n = int(input())
for i in range(n):
	count = 0
	cat = 0
	(n, k) = map(int, input().split())
	coords = list(map(int, input().split()))
	coords.sort(reverse=True)
	for x in coords:
		if x <= cat:
			break
		else:
			count += 1
			cat += n - x
	print(count)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort(reverse=True)
	(c, pos) = (0, 0)
	for i in a:
		if i <= pos:
			break
		pos += n - i
		c += 1
	print(c)


for _ in range(int(input())):
	[n, k] = [int(i) for i in input().split(' ')]
	l = [int(i) for i in input().split(' ')]
	step = n - 1
	l.sort()
	ans = 0
	for i in range(len(l) - 1, -1, -1):
		step -= n - l[i]
		if step >= 0:
			ans += 1
		else:
			break
	print(ans)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	x = [int(x) for x in input().split()]
	x.sort()
	x.reverse()
	total = 0
	answer = 0
	for i in x:
		difference = n - i
		if difference + total < n:
			total += difference
			answer += 1
		else:
			break
	print(answer)


n = int(input())
for i in range(n):
	(k, x) = input().split()
	(c, ans) = (0, 0)
	(k, x) = (int(k), int(x))
	l = sorted(list(map(int, input().split())))
	for i in range(x - 1, -1, -1):
		if l[i] <= c:
			break
		c += k - l[i]
		if c >= k:
			break
		else:
			ans += 1
	print(ans)


t = int(input())
L = []
for _ in range(t):
	(n, k) = map(int, input().split())
	l = sorted(list(map(int, input().split())), reverse=True)
	s = n - 1
	m = 0
	for i in l:
		togo = n - i
		if togo <= s:
			s -= togo
			m += 1
		else:
			break
	L.append(m)
for i in L:
	print(i)


for t in range(int(input())):
	(n, k) = map(int, input().split())
	mice = sorted(list(map(int, input().split())))
	(sm, ans) = (0, 0)
	for i in range(len(mice) - 1, -1, -1):
		if (sm := (sm + n - mice[i])) >= n:
			break
		ans += 1
	print(ans)


def save(n, k, x):
	x.sort()
	p = 0
	count = 0
	for i in range(k - 1, -1, -1):
		if x[i] > p:
			p += n - x[i]
			count += 1
		else:
			break
	return count
T = int(input())
for i in range(T):
	(n, k) = map(int, input().split())
	x = list(map(int, input().split()))
	print(save(n, k, x))


import sys
input = sys.stdin.readline

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

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

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

def invr():
	return map(int, input().split())
for _ in range(int(inp())):
	(n, k) = map(int, input().split())
	l = sorted(map(int, input().split()))
	ans = 0
	cat = 0
	for i in reversed(l):
		if cat >= i:
			break
		cat += n - i
		ans += 1
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	list1 = sorted(list(map(int, input().split())))[::-1]
	sums = 0
	idx = k
	for i in range(k):
		sums += n - list1[i]
		if sums >= n:
			idx = i
			break
	print(idx)


test = int(input())
while test > 0:
	p = list(map(int, input().split()))
	l = list(map(int, input().split()))
	l.sort(reverse=True)
	catpos = 0
	total = 0
	for i in l:
		if catpos < i:
			catpos += p[0] - i
			total += 1
		else:
			break
	print(total)
	test -= 1


def solve(n, k, locs):
	total = 0
	count = 0
	i = 0
	while i < k and locs[i] > total:
		count += 1
		total += n - locs[i]
		i += 1
	return count
ans = []
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	ans.append(solve(n, k, sorted(list(map(int, input().split())), reverse=True)))
print(*ans, sep='\n')


def saveMice(n, k, array):
	array.sort()
	cat_position = 0
	x = k - 1
	count = 0
	while x >= 0 and array[x] > cat_position:
		cat_position += n - array[x]
		x -= 1
		count += 1
	return count
t = int(input())
final = []
for _ in range(t):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	final.append(saveMice(n, k, l))
for _ in range(t):
	print(final[_])


def solve():
	[n, k] = [int(x) for x in input().split()]
	posiciones = [n - int(x) for x in input().split()]
	posiciones.sort()
	pasosUsados = 0
	i = 0
	salvados = 0
	while i < k and pasosUsados + posiciones[i] < n:
		pasosUsados = pasosUsados + posiciones[i]
		i = i + 1
		salvados = salvados + 1
	print(salvados)
t = int(input())
for i in range(t):
	solve()


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	i = 0
	saved = 0
	for x in a[::-1]:
		if i < x:
			jump = n - x
			i += jump
			saved += 1
		else:
			break
	print(saved)


for tc in range(int(input())):
	(n, k) = map(int, input().split())
	a = sorted(map(int, input().split()))
	(sm, cnt) = (0, 0)
	for i in a[::-1]:
		if i <= sm:
			break
		cnt += 1
		sm += n - i
	print(cnt)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	x = [int(x) for x in input().split()]
	x.sort(reverse=True)
	if k == 1:
		print(1)
	else:
		sums = 0
		i = 0
		while i < k and x[i] - sums > 0:
			sums += n - x[i]
			i += 1
		print(i)


def retornarVivos(t, lista):
	k = 0
	soma = 0
	for i in range(len(lista)):
		soma += t - int(lista[i])
		if soma >= t:
			return k
		k += 1
	return k
n = int(input())
while n > 0:
	x = input()
	(t, r) = x.split(' ')
	(t, r) = (int(t), int(r))
	lista = list(map(int, input().split(' ')))
	lista.sort()
	lista.reverse()
	print(retornarVivos(int(t), lista))
	n -= 1


def resolve():
	buraco = int(input().split(' ')[0])
	ratos_str = input().split(' ')
	ratos = sorted([buraco - int(x) for x in ratos_str])
	gato = 0
	ratos_salvos = 0
	while ratos_salvos < len(ratos) and gato < buraco - ratos[ratos_salvos]:
		gato += ratos[ratos_salvos]
		ratos_salvos += 1
	print(ratos_salvos)
ncasos = int(input())
for _ in range(ncasos):
	resolve()


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = sorted(map(int, input().split()))
	(c, ans) = (0, 0)
	for i in l[::-1]:
		if c >= i:
			break
		ans += 1
		c += n - i
	print(ans)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	w = sorted(map(int, input().split()), reverse=True)
	c = 0
	ans = 0
	for i in range(k):
		if c < w[i]:
			c += n - w[i]
			ans += 1
		else:
			break
	print(ans)


in_ = int(input())
for i in range(in_):
	[n, k] = map(int, input().split(' '))
	x = list(map(int, input().split(' ')))
	x.sort(reverse=True)
	m = 0
	a = 0
	for j in range(k):
		m += n - x[j]
		if m < n:
			a += 1
		else:
			break
	print(a)


def solve():
	(n, k) = (int(s) for s in input().split())
	a = [int(s) for s in input().split()]
	a.sort(reverse=True)
	cat_position = 0
	total = 0
	for i in range(k):
		if cat_position < a[i]:
			cat_position += n - a[i]
			total += 1
		else:
			break
	print(total)
t = 1
t = int(input())
for _ in range(t):
	solve()


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	A = list(map(int, input().split()))
	A.sort(reverse=True)
	ans = 0
	res = 0
	for i in range(k):
		if A[i] > res:
			res += n - A[i]
			ans += 1
		else:
			break
	print(ans)


for i in range(int(input())):
	ans = 'YES'
	(n, k) = map(int, input().split())
	s = sorted(list(map(int, input().split())), reverse=True)
	t1 = 0
	ans = 0
	for i in range(k):
		if s[i] > t1:
			t1 += n - s[i]
			ans += 1
		else:
			break
	print(ans)


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


import sys
N = int(200000.0 + 5)
sys.setrecursionlimit(N)

def charming():
	(n, k) = map(int, input().split())
	x = list(map(int, input().split()))
	x.sort(reverse=True)
	res = 0
	move = 0
	while res < k and x[res] > move:
		move += n - x[res]
		res += 1
	print(res)
for t in range(int(input())):
	charming()


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


from sys import stdin
import bisect
input = stdin.readline
ip = lambda : input().rstrip('\n')
IP = lambda : list(map(int, ip().split()))
for i in range(int(ip())):
	(n, k) = IP()
	lst = sorted(IP(), reverse=1)
	cur = 0
	ret = 0
	for i in lst:
		if cur >= i:
			break
		ret += 1
		cur += n - i
	print(ret)


t = int(input())
for case in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort(reverse=True)
	steps = 0
	count = 0
	for i in range(k):
		if steps >= a[i]:
			break
		else:
			count += 1
			steps += n - a[i]
	print(count)


def fun(n, k, arr):
	arr.sort()
	time = n - 1
	cnt = 0
	tot = 0
	i = k - 1
	while i > -1 and tot < time:
		tot += n - arr[i]
		i -= 1
		cnt += 1
	if tot > time:
		return cnt - 1
	return cnt
for i in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	ans = fun(n, k, arr)
	print(ans)


def solve():
	t = int(input())
	for _ in range(t):
		(n, k) = [int(s) for s in input().split()]
		x = sorted([int(s) for s in input().split()])
		ans = 0
		cat_x = 0
		mouse_i = k - 1
		while mouse_i > -1 and cat_x < x[mouse_i]:
			cat_x += n - x[mouse_i]
			ans += 1
			mouse_i -= 1
		print(ans)
solve()


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	arr = sorted(map(int, input().split()), reverse=True)
	res = [n - arr[0]]
	for i in range(1, len(arr)):
		res.append(res[-1] + n - arr[i])
		if res[-1] >= n:
			break
	else:
		print(len(res))
		continue
	print(max(1, len(res) - 1))


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


def new_func():
	for _ in range(int(input())):
		(n, k) = map(int, input().split())
		l = list(map(int, input().split()))
		l = sorted(l)
		ans = 0
		i = 0
		while i <= n:
			if i >= l[-1]:
				break
			i += n - l[-1]
			ans += 1
			l.pop()
			if len(l) == 0:
				break
		print(ans)
new_func()


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr.sort()
	(ans, cnt) = (0, 0)
	for i in range(len(arr) - 1, -1, -1):
		if cnt < arr[i]:
			ans += 1
			cnt += n - arr[i]
		else:
			break
	print(ans)


def test(n, arr):
	arr.sort()
	ans = 0
	(right, start) = (len(arr) - 1, 0)
	while right >= 0 and start < arr[right]:
		temp = n - arr[right]
		start += temp
		ans += 1
		right -= 1
	return ans
T = int(input())
for i in range(T):
	(n, k) = map(int, input().split())
	arr = [int(x) for x in input().split()]
	ans = test(n, arr)
	print(ans)


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


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


t = int(input())
for i in range(0, t):
	(n, k) = map(int, input().split())
	lst = list(map(int, input().split()))
	lst.sort()
	step = 0
	saftMice = 0
	for i in range(-1, -k - 1, -1):
		if lst[i] > step:
			saftMice += 1
			step += n - lst[i]
		else:
			break
	print(saftMice)


t = int(input())
for _ in range(t):
	(n, k) = list(map(int, input().split()))
	mices = list(map(int, input().split()))
	mices.sort(reverse=True)
	elapsedMin = 0
	savedMices = 0
	catPos = 0
	for mice in mices:
		if catPos >= mice:
			break
		miceNeededJumps = n - mice + elapsedMin
		elapsedMin = miceNeededJumps
		savedMices += 1
		catPos = miceNeededJumps
	print(savedMices)


t = int(input())
while t:
	t -= 1
	(n, k) = map(int, input().split())
	mice = list(map(int, input().strip().split()))
	mice = sorted(mice)
	(cat, ans) = (0, 0)
	for i in mice[::-1]:
		if cat >= i:
			break
		ans += 1
		cat += n - i
	print(ans)


t = int(input())
while t:
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort(reverse=True)
	time = ct = 0
	for i in l:
		if time + (n - i) >= n:
			break
		else:
			time += n - i
		ct += 1
	print(ct)
	t -= 1


t = int(input())
for i in range(t):
	sum = 0
	count = 0
	list_nk = list(map(int, input().split()))
	list_mice = list(map(int, input().split()))
	list_mice.sort(reverse=False)
	for j in range(list_nk[1] - 1, -1, -1):
		if sum >= list_mice[j]:
			break
		sum = sum + (list_nk[0] - list_mice[j])
		count += 1
	print(count)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort(reverse=True)
	ans = 0
	t = n
	for i in l:
		if t - (n - i) > 0:
			t -= n - i
			ans += 1
		else:
			break
	print(ans)


t = int(input())

def solve():
	(n, k) = map(int, input().split())
	arr = sorted(list(map(int, input().split())))
	rem = n - 1
	ans = 0
	for i in reversed(arr):
		if rem <= 0:
			break
		if n - i <= rem:
			rem -= n - i
			ans += 1
		else:
			break
	print(ans)
for i in range(t):
	solve()


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	x = sorted(map(int, input().split()), reverse=True)
	cat_position = 0
	count_saved_mouses = 0
	for i in range(k):
		if x[i] <= cat_position:
			break
		count_saved_mouses += 1
		cat_position += n - x[i]
	print(count_saved_mouses)


for i in range(int(input())):
	(n, k) = list(map(int, input().split()))
	cum = 0
	mice = list(map(int, input().split()))
	mice.sort()
	c = 0
	for j in mice[::-1]:
		if cum < j:
			c += 1
		else:
			print(c)
			break
		cum += n - j
	else:
		print(c)


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


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort(reverse=True)
	(i, c) = (0, 0)
	while i < k and c < a[i]:
		c += n - a[i]
		i += 1
	print(i)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	x = list(map(int, input().split()))
	x.sort()
	time = 0
	res = 0
	cat = 0
	for i in range(k - 1, -1, -1):
		if cat < x[i]:
			res += 1
			cat += n - x[i]
		else:
			break
	print(res)


import sys
input = sys.stdin.readline

def solve():
	(n, k) = map(int, input().split())
	x = list(map(int, input().split()))
	x.sort(reverse=True)
	c = 0
	ans = 0
	for xi in x:
		if xi > c:
			ans += 1
			c += n - xi
		else:
			break
	print(ans)
for _ in range(int(input())):
	solve()


from math import gcd
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	mice = sorted(map(int, input().split()))[:k]
	cat = 0
	while mice and mice[-1] > cat:
		steps = n - mice[-1]
		mice.pop()
		cat += steps
	print(k - len(mice))


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort(reverse=True)
	mo = 0
	ca = 0
	for i in range(k):
		tc = n - a[i]
		if ca >= a[i]:
			break
		else:
			mo += 1
			ca += tc
	print(mo)