C. Составление двух команд
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Под вашим контролем находятся $$$n$$$ студентов и вам нужно составить ровно две команды, состоящие из некоторого подмножества ваших студентов. У каждого студента есть свой собственный навык, навык $$$i$$$-го студента обозначен числом $$$a_i$$$ (у различных студентов могут быть одинаковые навыки).

Итак, о командах. Во-первых, эти две команды должны быть одинакового размера. Есть еще два требования:

  • Первая команда должна состоять из студентов с различными навыками (то есть нет одинаковых навыков среди студентов первой команды).
  • Вторая команда должна состоять из студентов с одинаковыми навыками (то есть все навыки среди студентов второй команды равны между собой).

Отметим, что допустимо, что какой-то студент первой команды имеет такой же навык, как и студент второй команды.

Рассмотрим несколько примеров (перечислены навыки для команд):

  • $$$[1, 2, 3]$$$, $$$[4, 4]$$$ не являются подходящей парой команд, потому что их размеры должны быть одинаковыми;
  • $$$[1, 1, 2]$$$, $$$[3, 3, 3]$$$ не являются подходящей парой команд, потому что первая команда не должна включать студентов с одинаковыми навыками;
  • $$$[1, 2, 3]$$$, $$$[3, 4, 4]$$$ не являются подходящей парой команд, потому что вторая команда должна включать студентов с одинаковыми навыками;
  • $$$[1, 2, 3]$$$, $$$[3, 3, 3]$$$ — подходящая пара команд;
  • $$$[5]$$$, $$$[6]$$$ — тоже подходящая пара команд.

Ваша задача — найти максимально возможный размер команд $$$x$$$, для которого возможно составить подходящую пару команд, где каждая команда имеет размер $$$x$$$ (в первой команде все навыки различны, во второй — все навыки равны между собой). Студент не может входить более чем в одну команду.

Вам нужно ответить на $$$t$$$ независимых наборов входных данных.

Входные данные

Первая строка теста содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов тестовых данных. Затем следуют $$$t$$$ наборов тестовых данных.

Первая строка набора содержит одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — количество студентов. Вторая строка набора содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$), где $$$a_i$$$ — это навык $$$i$$$-го студента. У различных студентов могут быть одинаковые навыки.

Гарантируется, что сумма чисел $$$n$$$ по всем наборам тестовых данных не превосходит $$$2 \cdot 10^5$$$ ($$$\sum n \le 2 \cdot 10^5$$$).

Выходные данные

Для каждого набора тестовых данных выведите ответ на него — максимально возможный размер команд $$$x$$$, для которого возможно составить подходящую пару команд, где каждая команда имеет размер $$$x$$$.

Пример
Входные данные
4
7
4 2 4 1 4 3 4
5
2 1 5 4 3
1
1
4
1 1 1 3
Выходные данные
3
1
0
2
Примечание

В первом наборе тестовых данных примера возможно составить две команды размера $$$3$$$: первая команда может иметь вид $$$[1, 2, 4]$$$, вторая команда может иметь вид $$$[4, 4, 4]$$$. Заметим, есть и другие способы выбрать две команды размера $$$3$$$, которые соответствуют требованиям выше.