There are $n$ workers and $m$ tasks. The workers are numbered from $1$ to $n$. Each task $i$ has a value $a_i$ — the index of worker who is proficient in this task.

Every task should have a worker assigned to it. If a worker is proficient in the task, they complete it in $1$ hour. Otherwise, it takes them $2$ hours.

The workers work in parallel, independently of each other. Each worker can only work on one task at once.

Assign the workers to all tasks in such a way that the tasks are completed as early as possible. The work starts at time $0$. What's the minimum time all tasks can be completed by?


-----Input-----

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of testcases.

The first line of each testcase contains two integers $n$ and $m$ ($1 \le n \le m \le 2 \cdot 10^5$) — the number of workers and the number of tasks.

The second line contains $m$ integers $a_1, a_2, \dots, a_m$ ($1 \le a_i \le n$) — the index of the worker proficient in the $i$-th task.

The sum of $m$ over all testcases doesn't exceed $2 \cdot 10^5$.


-----Output-----

For each testcase, print a single integer — the minimum time all tasks can be completed by.


-----Examples-----

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


-----Note-----

In the first testcase, the first worker works on tasks $1$ and $3$, and the second worker works on tasks $2$ and $4$. Since they both are proficient in the corresponding tasks, they take $1$ hour on each. Both of them complete $2$ tasks in $2$ hours. Thus, all tasks are completed by $2$ hours.

In the second testcase, it's optimal to assign the first worker to tasks $1, 2$ and $3$ and the second worker to task $4$. The first worker spends $3$ hours, the second worker spends $2$ hours (since they are not proficient in the taken task).

In the third example, each worker can be assigned to the task they are proficient at. Thus, each of them complete their task in $1$ hour.

Difficulty: MEDIUM
Tags: Sorting

Amortized analysis

Implementation

Greedy algorithms
Skill types: Sorting

Amortized analysis

Greedy algorithms

Starter code:

Solutions:
def moze(v, r, n):
	s = 0
	for i in range(n):
		if r[i] - v < 0:
			s += (-r[i] + v) // 2
		else:
			s -= r[i] - v
	if s >= 0:
		return True
	return False

def nadji(r, n, m):
	l = (m - 1) // n + 1
	right = 2 * l
	iz = -1
	while l <= right:
		sredina = (l + right) // 2
		if moze(sredina, r, n):
			right = sredina - 1
			iz = sredina
			continue
		else:
			l = sredina + 1
	return iz

def resi():
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	r = [0] * n
	for i in range(m):
		r[a[i] - 1] += 1
	print(nadji(r, n, m))
for _ in range(int(input())):
	resi()


tc = int(input())
while tc > 0:
	A = [int(i) for i in input().split(' ')]
	B = [int(i) for i in input().split(' ')]
	n = A[0]
	m = A[1]
	w = [0 for i in range(n)]
	for i in B:
		w[i - 1] += 1
	ans = 0
	while m != 0:
		w.sort(reverse=True)
		for i in range(n):
			if m > 0 and w[i] > 0:
				w[i] = w[i] - 1
				m = m - 1
			elif m > 0:
				if type(w[i]) == int:
					m = m - 1
					w[i] = w[i] - 1.0
				else:
					w[i] = int(w[i])
			else:
				w[i] = int(w[i])
		ans += 1
	if type(sum(w)) == int:
		print(ans)
	else:
		print(ans + 1)
	tc = tc - 1


def solve(n, m, pros):
	prof = [0 for i in range(n)]
	for _pro in pros:
		prof[_pro - 1] += 1
	for t in range(0, m * 2 + 1):
		capacity = 0
		for w in range(n):
			prof_completed = min(t, prof[w])
			non_prof_completed = 0
			if prof_completed < t:
				non_prof_completed = (t - prof_completed) // 2
			capacity += non_prof_completed + prof_completed
		if capacity >= m:
			return t
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split(' '))
	print(solve(n, m, map(int, input().split(' '))))


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	l = [0] * n
	for i in list(map(int, input().split())):
		l[i - 1] += 1
	cur = 0
	time = 0
	while m > 0:
		time += 1
		num = 0
		for i in range(n):
			if l[i] != 0 and num < m:
				l[i] -= 1
				num += 1
		m -= num
		x = n - num - cur
		cur = min(m, x)
		m -= cur
	if cur != 0:
		time += 1
	print(time)


from heapq import *
from collections import Counter, defaultdict

def isPos(cnt, x):
	rem = 0
	for i in range(len(cnt)):
		if cnt[i] > x:
			rem += (cnt[i] - x) * 2
		elif x - cnt[i] >= 2:
			rem -= (x - cnt[i]) // 2 * 2
			if rem <= 0:
				return True
	return rem == 0
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	cnt = [0 for i in range(n)]
	for i in a:
		cnt[i - 1] += 1
	cnt.sort(reverse=True)
	(low, high) = (cnt[-1], cnt[0])
	while low < high:
		mid = (low + high) // 2
		if not isPos(cnt, mid):
			low = mid + 1
		else:
			high = mid
	print(high)


T = int(input())
while T:
	T -= 1
	(n, m) = map(int, input().split())
	freq = [0] * n
	arr = list(map(int, input().split()))
	for ele in arr:
		freq[ele - 1] += 1
	count = [0] * (m + 1)
	for fre in freq:
		count[fre] += 1
	for i in range(1, m + 1):
		count[i] += count[i - 1]
	done = 0
	prev = 0
	for hr in range(1, m + 1):
		done = done + prev + (n - count[hr - 1])
		if done >= m:
			break
		prev = count[hr - 1] - prev
	print(hr)


def solve(n: int, m: int, arr):
	counter = [0 for _ in range(n + 1)]
	for val in arr:
		counter[val] += 1
	minimal_time = 0
	maximal_time = len(arr) // n * 2 + 5
	while maximal_time - minimal_time > 1:
		time = (maximal_time + minimal_time) // 2
		amount_of_task_solved = 0
		for i in range(1, n + 1):
			solved = min(time, counter[i])
			if solved < time:
				solved += (time - solved) // 2
			amount_of_task_solved += solved
		if amount_of_task_solved >= m:
			maximal_time = time
		else:
			minimal_time = time
	return maximal_time
T = int(input())
for _ in range(T):
	(n, m) = map(int, input().split())
	arr = list(map(int, input().split()))
	print(solve(n, m, arr))


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	dela = [0] * n
	for x in a:
		dela[x - 1] += 1
	dela.sort()
	skol = [0] * (dela[-1] + 1)
	s = 0
	kol = n
	for x in range(len(dela)):
		if dela[x] != s:
			skol[s] = kol
			kol = n - x
			for y in range(s + 1, dela[x] + 1):
				skol[y] = kol
			s = dela[x]
	skol[-1] = kol
	S = m
	ph = [None] * len(skol)
	ph[0] = 0
	for x in range(1, len(skol)):
		ph[x] = n - ph[x - 1] - skol[x]
	for x in range(len(skol) - 1, -1, -1):
		S += skol[x]
		if n * (x - 1) - ph[x - 1] < S:
			print(x)
			break


def check(time):
	total = 0
	for i in range(1, n + 1):
		if workers[i] >= time:
			total -= workers[i] - time
		else:
			total += (time - workers[i]) // 2
	if total >= 0:
		return True
	else:
		return False

def search(left, right):
	while left <= right:
		mid = (left + right) // 2
		if check(mid) and (not check(mid - 1)):
			return mid
		elif check(mid):
			right = mid - 1
		else:
			left = mid + 1
	return -1
T = int(input())
for _ in range(T):
	(n, m) = map(int, input().split())
	good = list(map(int, input().split()))
	workers = dict()
	for i in range(1, n + 1):
		workers[i] = 0
	for person in good:
		workers[person] += 1
	print(search(1, 4 * m // n))


import heapq
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	st = [0 for _ in range(n)]
	for v in a:
		st[v - 1] += 1
	mv = max(st)
	z = [0 for _ in range(mv + 1)]
	for v in st:
		z[v] += 1
	l = 0
	r = mv
	while r - l > 2:
		if z[l] == 0:
			l += 1
		elif z[r] == 0:
			r -= 1
		else:
			z[r] -= 1
			z[r - 1] += 1
			z[l] -= 1
			z[l + 2] += 1
	for r in range(mv, -1, -1):
		if z[r] > 0:
			print(r)
			break


from heapq import heappop, heappush, heapify
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	(minheap, maxheap) = ([0] * n, [0] * n)
	for i in a:
		minheap[i - 1] += 1
		maxheap[i - 1] -= 1
	heapify(minheap)
	heapify(maxheap)
	if minheap[0] == -maxheap[0]:
		print(minheap[0])
		continue
	while -maxheap[0] - minheap[0] > 2:
		(maxe, mine) = (heappop(maxheap), heappop(minheap))
		heappush(maxheap, maxe + 1)
		heappush(minheap, mine + 2)
	print(-maxheap[0])


def get_sum_strength(tasks, hours):
	s_sum = 0
	for task in tasks:
		s_sum += min(task, hours) + int(0.5 * max(hours - task, 0))
	return s_sum
for _ in range(int(input())):
	(n, m) = list(map(int, input().split()))
	a = list(map(lambda x: int(x) - 1, input().split()))
	tasks = [0] * n
	for task in a:
		tasks[task] += 1
	(l, r) = (1, int(2 * m / n) + 1)
	hours = (l + r) // 2
	s_sum = get_sum_strength(tasks, hours)
	while not l == r:
		if s_sum < m:
			l = hours + 1
		else:
			r = hours
		hours = (l + r) // 2
		s_sum = get_sum_strength(tasks, hours)
	print(hours)


def solve(d):
	total = sum((d if x > d else x + (d - x) // 2 for x in c))
	return total >= m
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	c = [0] * n
	for x in map(int, input().split()):
		c[x - 1] += 1
	low = 0
	high = max(c)
	while high - low > 1:
		mid = (high + low) // 2
		if solve(mid):
			high = mid
		else:
			low = mid
	print(high)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	c = [0] * n
	nums = map(int, input().split())
	for i in nums:
		c[i - 1] += 1
	low = 0
	high = max(c)
	while high - low > 1:
		mid = (high + low) // 2
		if sum((mid if x >= mid else x + (mid - x) // 2 for x in c)) >= m:
			high = mid
		else:
			low = mid
	print(high)


t = int(input())
while t:
	t -= 1
	(n, m) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	arr = [0] * n
	for x in a:
		arr[x - 1] += 1
	l = 1
	r = max(arr)

	def can(time):
		remain = 0
		for x in arr:
			if x >= time:
				remain += x - time
			else:
				remain -= (time - x) // 2
		if remain <= 0:
			return True
		else:
			return False
	while l <= r:
		mid = (l + r) // 2
		if can(mid):
			r = mid - 1
		else:
			l = mid + 1
	print(l)


def b(t):
	bal = 0
	for i in f:
		if i >= t:
			bal += i - t
		else:
			bal -= (t - i) // 2
	return bal <= 0
out = []
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = [int(i) for i in input().split()]
	f = [0] * n
	for i in a:
		f[i - 1] += 1
	l = 0
	r = 2 * m
	while r - l > 1:
		mid = (r + l) // 2
		if not b(mid):
			l = mid
		else:
			r = mid
	out.append(r)
for i in out:
	print(i)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	b = [0 for i in range(1, n + 1, 1)]
	for i in range(m):
		b[a[i] - 1] += 1
	t = max(b)
	l = 0
	while t - l > 1:
		mid = (l + t) // 2
		if sum((mid if x > mid else x + (mid - x) // 2 for x in b)) >= m:
			t = mid
		else:
			l = mid
	print(t)


for h in range(int(input())):
	(n, m) = map(int, input().split())
	x = list(map(int, input().split()))
	vec = [0] * n
	for i in x:
		vec[i - 1] += 1
	vec.sort(reverse=True)
	(l, r) = (0, m * 2)
	v = m * 2
	while l <= r:
		m = (l + r) // 2
		ct = 0
		for i in vec:
			if i > m:
				ct += i - m
			elif ct > 0 and i < m:
				ct = max(ct - (m - i) // 2, 0)
		if ct == 0:
			r = m - 1
			v = min(v, m)
		else:
			l = l + 1
	print(v)


MOD = 10 ** 9 + 7
fac_mem = [1]

def fac(n):
	while len(fac_mem) < n + 1:
		fac_mem.append(fac_mem[-1] * len(fac_mem) % MOD)
	return fac_mem[n]

def perm(n, k):
	return fac(n) * pow(fac(k), MOD - 2, MOD) % MOD

def comb(n, k):
	return fac(n) * pow(fac(k) * fac(n - k) % MOD, MOD - 2, MOD) % MOD

class Tree:

	def __init__(self, id):
		self.id = id
		self.parent = None
		self.children = []

	def __repr__(self):
		if self.children:
			return f'{self.id} -> [' + ', '.join((str(c) for c in self.children)) + ']'
		else:
			return str(self.id)
for case in range(int(input())):
	(n, m) = [int(j) for j in input().split()]
	a = [int(j) for j in input().split()]
	l = [0] * n
	for i in a:
		l[i - 1] += 1
	l = sorted(l)
	a = 0
	b = m
	while a != b:
		mid = (a + b) // 2
		ones = 0
		twos = 0
		for i in l:
			if i > mid:
				ones += i - mid
			else:
				twos += (mid - i) // 2
		if twos < ones:
			a = mid + 1
		else:
			b = mid
	print(a)


def helper(p, t, n):
	rem = 0
	for i in range(n):
		if p[i] > t:
			rem = rem + (p[i] - t)
		else:
			v = (t - p[i]) // 2
			rem = rem - v
	return rem <= 0
for i in range(int(input())):
	(n, m) = map(int, input().split())
	arr = list(map(int, input().split()))
	p = [0] * m
	for i in range(m):
		p[arr[i] - 1] += 1
	l = 0
	r = m * 2
	while l < r:
		mid = (l + r) // 2
		if helper(p, mid, n):
			r = mid
		else:
			l = mid + 1
	print(l)


from collections import defaultdict
from sys import stdin
input = stdin.readline

def ch(x):
	ans = 0
	res = 0
	for i in range(n):
		if x >= d[i]:
			ans += (x - d[i]) // 2
		else:
			res += d[i] - x
	return ans >= res
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	d = [0] * n
	f = list(map(int, input().split()))
	for i in f:
		d[i - 1] += 1
	l = 0
	r = 2 * m
	while l < r:
		mid = l + r >> 1
		if ch(mid):
			r = mid
		else:
			l = mid + 1
	print(l)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	cnt = [0] * n
	for i in list(map(int, input().split())):
		cnt[i - 1] += 1
	(lo, hi) = (0, max(cnt))
	while lo < hi:
		mid = lo + hi >> 1
		s = 0
		for i in cnt:
			if i > mid:
				s += mid
			else:
				s += i + (mid - i) // 2
		if s >= m:
			hi = mid
		else:
			lo = mid + 1
	print(hi)


import heapq
t = int(input())
for _ in range(t):
	(n, m) = list(map(int, input().strip().split(' ')))
	p = list(map(int, input().strip().split(' ')))
	hours = [0 for _ in range(n)]
	for item in p:
		hours[item - 1] += 1
	min_heap = []
	max_heap = []
	for (i, item) in enumerate(hours):
		heapq.heappush(min_heap, (item, i + 1))
		heapq.heappush(max_heap, (-item, i + 1))
	(min_hour, min_worker) = heapq.heappop(min_heap)
	(max_hour, max_worker) = heapq.heappop(max_heap)
	max_hour = abs(max_hour)
	while max_hour - 1 >= min_hour + 2:
		max_hour -= 1
		min_hour += 2
		heapq.heappush(max_heap, (-max_hour, max_worker))
		heapq.heappush(min_heap, (min_hour, min_worker))
		(min_hour, min_worker) = heapq.heappop(min_heap)
		(max_hour, max_worker) = heapq.heappop(max_heap)
		max_hour = abs(max_hour)
	print(max_hour)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	l = list(map(int, input().split()))
	d = [0] * n
	for i in l:
		d[i - 1] += 1
	t = sorted(d)
	ans = max(t)
	i = 0
	j = t[-1]
	while i <= j:
		md = (i + j) // 2
		a = 0
		b = 0
		for x in t:
			if x > md:
				a += x - md
			elif x < md:
				b += (md - x) // 2
		if a <= b:
			ans = min(ans, md)
			j = md - 1
		else:
			i = md + 1
	print(ans)


class ScheduleManagement:

	def __init__(self, n, m, a):
		self.n = n
		self.m = m
		self.a = a
		self.cnt = [0] * self.n
		for i in self.a:
			self.cnt[i - 1] += 1

	def isPossible(self, t):
		work2hr = 0
		work1hr = 0
		for i in range(self.n):
			if t > self.cnt[i]:
				work2hr += (t - self.cnt[i]) // 2
			else:
				work1hr += self.cnt[i] - t
		if work2hr >= work1hr:
			return True
		return False

	def solve(self):
		l = 0
		r = 2 * self.m
		result = 2 * self.m
		while l <= r:
			m = (l + r) // 2
			if self.isPossible(m):
				result = m
				r = m - 1
			else:
				l = m + 1
		print(result)
		return
T = int(input())
while T:
	T -= 1
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	ScheduleManagement(n, m, a).solve()


t = int(input())
for _ in range(t):
	(n, m) = [int(i) for i in input().split()]
	a = [int(i) for i in input().split()]
	worker = [0] * n
	for x in a:
		worker[x - 1] += 1
	high = max(worker)
	low = 0
	while low <= high:
		mid = low + (high - low) // 2
		tasks = 0
		for x in worker:
			if x >= mid:
				tasks += mid
			else:
				tasks += x + (mid - x) // 2
		if tasks >= m:
			high = mid - 1
		else:
			low = mid + 1
	print(low)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	nums = list(map(int, input().split()))
	tmp = [0] * n
	for num in nums:
		tmp[num - 1] += 1
	(l, r) = (1, m * 2)
	while l <= r:
		m = (l + r) // 2
		unperformed_nonproficient_work = 0
		res_time = 0
		for x in tmp:
			if x > m:
				unperformed_nonproficient_work += x - m
			else:
				y = m - x
				res_time += y // 2
		if res_time >= unperformed_nonproficient_work:
			r = m - 1
		else:
			l = m + 1
	print(l)


from sys import stdin
input = stdin.readline
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	cnt = [0] * n
	for i in list(map(int, input().split())):
		cnt[i - 1] += 1
	(lo, hi) = (0, max(cnt))
	while lo < hi:
		mid = lo + hi >> 1
		s = 0
		for i in cnt:
			if i > mid:
				s += mid
			else:
				s += i + (mid - i) // 2
		if s >= m:
			hi = mid
		else:
			lo = mid + 1
	print(hi)


for _ in range(int(input())):
	(n, m) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	p = [0] * n
	for i in arr:
		p[i - 1] += 1
	l = 0
	r = 2 * m
	while l < r:
		x = (l + r) // 2
		done = 0
		for i in p:
			if i <= x:
				done += i + (x - i) // 2
			else:
				done += x
		if done >= m:
			r = x
		else:
			l = x + 1
	print(l)


t = int(input())
while t:
	s = input().split()
	(n, m) = map(int, s)
	s = input().split()
	a = list(map(lambda x: int(x) - 1, s))
	cnt = {i: 0 for i in range(n)}
	for i in a:
		cnt[i] += 1

	def isvalid(x):
		extra = 0
		helpn = 0
		for i in range(n):
			if x > cnt[i]:
				extra += (x - cnt[i]) // 2
			else:
				helpn += cnt[i] - x
		if extra >= helpn:
			return True
		else:
			return False
	(low, high) = (1, 2 * m)
	while low < high:
		mid = (low + high) // 2
		if isvalid(mid):
			high = mid
			ans = mid
		else:
			low = mid + 1
			ans = low
	print(ans)
	t -= 1


from turtle import left
t = int(input())

def validate(n, m, a, q):
	workers = [0 for _ in range(n)]
	left_over = 0
	for i in range(m):
		wi = a[i] - 1
		if workers[wi] < q:
			workers[wi] += 1
		else:
			left_over += 1
	for i in range(n):
		left_over -= (q - workers[i]) // 2
		if left_over <= 0:
			break
	if left_over <= 0:
		return True
	else:
		return False
for _ in range(t):
	(n, m) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	low = 1
	high = 4 * 10 ** 5
	while low <= high:
		mid = (high + low) // 2
		if validate(n, m, a, mid):
			high = mid - 1
		else:
			low = mid + 1
	print(low)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	mp = {i: 0 for i in range(1, n + 1)}
	a = list(map(int, input().split()))
	for v in a:
		mp[v] += 1

	def check(time):
		t_c = 0
		for k in mp:
			if mp[k] > time:
				t_c += time
			else:
				t_c += mp[k] + (time - mp[k]) // 2
		return t_c >= m
	(low, high) = (1, m * 2)
	while low <= high:
		mid = (low + high) // 2
		if check(mid):
			high = mid - 1
		else:
			low = mid + 1
	print(high + 1)


test = int(input())
for t in range(test):
	(n, m) = list(map(int, input().split()))
	nums = list(map(int, input().split()))
	counter = [0] * n
	for num in nums:
		counter[num - 1] += 1
	minimum = 1
	maximum = 2 * m
	ans = maximum
	while minimum <= maximum:
		mid = (minimum + maximum) // 2
		left = 0
		help = 0
		for i in range(n):
			if mid > counter[i]:
				help += (mid - counter[i]) // 2
			else:
				left += counter[i] - mid
		flag = help >= left
		if flag:
			ans = mid
			maximum = mid - 1
		else:
			minimum = mid + 1
	print(ans)


a = []
(n, m) = (0, 0)

def bis(lef, rig):
	if rig - lef == 1:
		return rig
	time = [0] * n
	mid = lef + (rig - lef) // 2
	surp = 0
	for i in a:
		if time[i - 1] < mid:
			time[i - 1] += 1
		else:
			surp += 1
	for i in time:
		surp -= (mid - i) // 2
	if surp <= 0:
		return bis(lef, mid)
	else:
		return bis(mid, rig)
t = int(input())
for i in range(t):
	[n, m] = list(map(int, input().split()))
	a = list(map(int, input().split()))
	print(int(bis(0, m * 2)))


from cmath import *
from decimal import *
from re import I
import sys
input_ = sys.stdin.readline

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

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

def solves():
	(n, m) = _input()
	a = _list()
	cnt = [0] * n
	for i in a:
		cnt[i - 1] += 1
	(ng, ok) = (0, max(cnt))
	while ok - ng > 1:
		m = (ng + ok) // 2
		b = 0
		for i in cnt:
			b += max(0, i - m)
		for i in cnt:
			if i < m:
				b -= (m - i) // 2
		if b > 0:
			ng = m
		else:
			ok = m
	print(ok)
t = 1
t = int(input())
for _ in range(0, t):
	solves()


import sys
import math
from bisect import bisect_right as br
from collections import deque
from itertools import combinations as cb

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

def str_arr():
	return list(map(str, sys.stdin.readline().strip().split()))

def input():
	return sys.stdin.readline().strip()
for _ in range(int(input())):
	(p, n) = int_arr()
	arr = int_arr()
	task = [0 for i in range(p)]
	for i in arr:
		task[i - 1] += 1
	k = 1
	j = 200001
	ans = float('inf')
	while k <= j:
		mid = (k + j) // 2
		extra = 0
		need = 0
		for i in range(p):
			if mid - task[i] >= 0:
				extra += (mid - task[i]) // 2
			else:
				need += mid - task[i]
		if extra + need >= 0:
			ans = min(ans, mid)
			j = mid - 1
		else:
			k = mid + 1
	print(ans)


T = int(input())
for t in range(0, T):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	hm = [0 for i in range(0, n)]
	for item in a:
		hm[item - 1] += 1
	l = 0
	r = m
	while l <= r:
		need_help = 0
		give_help = 0
		mid = (l + r) // 2
		for i in range(0, n):
			if hm[i] - mid > 0:
				need_help += hm[i] - mid
			else:
				give_help = give_help + (mid - hm[i]) // 2
		if give_help >= need_help:
			ans = mid
			r = mid - 1
		else:
			l = mid + 1
	print(ans)


t = int(input())
while t:
	(n, m) = list(map(int, input().split()))
	lst = list(map(int, input().split()))
	a = [0 for i in range(n + 1)]
	for k in lst:
		a[k] += 1
	up = 2 * m
	low = 0
	ans = 2 * m
	while low <= up:
		mid = low + (up - low) // 2
		work = 0
		time = 0
		for i in range(1, n + 1):
			if mid >= a[i]:
				time += (mid - a[i]) // 2
			else:
				work += a[i] - mid
		if time >= work:
			up = mid - 1
			ans = min(ans, mid)
		else:
			low = mid + 1
	print(ans)
	t -= 1


def max_tasks_in_time(t):
	can_complete = 0
	for w in range(n):
		tasks_as_profi = min(prof[w], t)
		can_complete += tasks_as_profi + (t - tasks_as_profi) // 2
	return can_complete
tests = int(input())
ans = []
for _ in range(tests):
	(n, m) = map(int, input().split(' '))
	task_profi = input().split(' ')
	prof = [0] * n
	for (i, el) in enumerate(task_profi):
		p = int(el)
		prof[p - 1] += 1
	l = 1
	r = 2 * m
	time = 10 ** 9
	while l <= r:
		t = (l + r) // 2
		max_tasks = max_tasks_in_time(t)
		if max_tasks >= m:
			time = min(t, time)
			r = t - 1
		else:
			l = t + 1
	ans.append(time)
for i in ans:
	print(i)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	arr = list(map(int, input().split()))
	d = dict([(i, 0) for i in range(1, n + 1)])
	for i in arr:
		d[i] += 1
	(l, r) = (0, m)
	while l < r:
		x = (l + r) // 2
		(t, w) = (0, 0)
		for i in range(1, n + 1):
			if d[i] <= x:
				t += (x - d[i]) // 2
			else:
				w += d[i] - x
		if t >= w:
			r = x
		else:
			l = x + 1
	print(l)


test = int(input())
while test:
	(n, m) = map(int, input().split())
	a = [int(x) for x in input().split()]
	low = 1
	high = 2 * m
	work = [0] * (n + 1)
	for i in a:
		work[i] += 1
	ans = 0
	while low <= high:
		mid = (low + high) // 2
		left_task = 0
		for i in range(1, n + 1):
			if work[i] <= mid:
				left_task -= (mid - work[i]) // 2
			else:
				left_task += work[i] - mid
		if left_task <= 0:
			ans = mid
			high = mid - 1
		else:
			low = mid + 1
	print(ans)
	test -= 1


t = int(input())
while t > 0:
	t -= 1
	(n, m) = list(map(int, input().split()))
	proficiency = list(map(int, input().split()))
	lower = 1
	upper = 2 * m
	frequency = {}
	for i in range(1, n + 1):
		frequency[i] = 0
	for x in proficiency:
		frequency[x] += 1
	ans = 0
	while lower <= upper:
		mid = (lower + upper) // 2
		left = 0
		helpOther = 0
		for i in range(1, n + 1):
			if mid > frequency[i]:
				helpOther += (mid - frequency[i]) // 2
			else:
				left += frequency[i] - mid
		if left <= helpOther:
			upper = mid - 1
			ans = mid
		else:
			lower = mid + 1
	print(ans)


q = int(input())
for _ in range(q):
	(n, m) = map(int, input().split())
	a = list(map(lambda x: int(x) - 1, input().split()))
	b = [0] * n
	for i in range(m):
		b[a[i]] += 1
	l = 0
	r = 1000000
	while r - l > 1:
		m = (l + r) // 2
		cnt = 0
		for i in range(n):
			if m > b[i]:
				cnt += (m - b[i]) // 2
			else:
				cnt -= b[i] - m
		if cnt >= 0:
			r = m
		else:
			l = m
	print(r)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	d = dict()
	l = list(map(int, input().split()))
	for i in range(1, n + 1):
		d[i] = 0
	for i in l:
		d[i] += 1
	mxt = m
	lo = 1
	hi = mxt
	while lo < hi:
		mid = (lo + hi) // 2
		z = mid * 1
		extra = 0
		rem = 0
		for k in d:
			if z >= d[k]:
				dif = z - d[k]
				y = dif // 2
				extra += y
			else:
				dif = d[k] - z
				rem += dif
		if extra >= rem:
			hi = mid
		else:
			lo = mid + 1
	print(lo)


t = int(input())
while t > 0:
	t -= 1
	(n, m) = map(int, input().split())
	arr = list(map(int, input().split()))
	(low, high) = (-1, m + 1)
	while low < high - 1:
		mid = (high + low) // 2
		freq = [0] * n
		for x in arr:
			freq[x - 1] += 1
		count = 0
		for x in freq:
			if mid <= x:
				count += mid
			else:
				count += (mid + x) // 2
		if count >= m:
			high = mid
		else:
			low = mid
	print(high)