G. Коробка с конфетами (усложненная версия)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Эта задача — усложненная версия задачи D из этого же самого контеста с дополнительными ограничениями и заданиями.

В коробке с конфетами находятся $$$n$$$ конфет. Тип $$$i$$$-й конфеты равен $$$a_i$$$ ($$$1 \le a_i \le n$$$).

Вы хотите приготовить подарок, используя некоторые из этих конфет, со следующим ограничением: количества конфет каждого типа, находящегося в подарке, должны быть различны (то есть, например, подарок, имеющий две конфеты типа $$$1$$$ и две конфеты типа $$$2$$$ является плохим).

Возможно, что некоторые типы конфет могут вообще не находиться в подарке. Также возможно, что не все конфеты каких-то типов будут взяты в подарок.

Вы очень любите некоторые конфеты из коробки и не хотите их включать в подарок (вы бы предпочли сами их съесть). Для каждой конфеты задано число $$$f_i$$$, которое равно $$$0$$$, если вы хотите оставить $$$i$$$-ю конфету себе, или $$$1$$$, если вы вполне можете отдать ее, и это не вызовет у вас никаких отрицательных эмоций. Возможно, что у двух конфет одного типа могут быть разные значения $$$f_i$$$.

Вы хотите собрать как можно больше конфет в подарок — но, с другой стороны, вы не хотите отдавать слишком много конфет из тех, которые бы предпочли съесть сами. Поэтому вы хотите посчитать максимальное число конфет, которое может быть включено в подарок, а среди всех способов выбрать максимальное число конфет в подарке — максимально возможное количество конфет с $$$f_i = 1$$$.

Вам необходимо ответить на $$$q$$$ независимых запросов.

Если Вы программируете на Python, рассмотрите возможность отправки решения на PyPy, а не на Python, когда будете отправлять свой код.

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

Первая строка входных данных содержит одно целое число $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) — количество запросов.

Первая строка каждого запроса содержит одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — количество конфет.

Затем следует $$$n$$$ строк, каждая из которых содержит два целых числа $$$a_i$$$ и $$$f_i$$$ ($$$1 \le a_i \le n$$$, $$$0 \le f_i \le 1$$$), где $$$a_i$$$ — тип $$$i$$$-й конфеты, а $$$f_i$$$ обозначает, хотите ли вы оставить $$$i$$$-ю конфету себе ($$$0$$$ — если вы хотите ее оставить, $$$1$$$ — если вы вполне можете ее отдать).

Гарантируется, что сумма $$$n$$$ по всем запросам не превосходит $$$2 \cdot 10^5$$$.

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

Для каждого запроса выведите два целых числа:

  • максимальное количество конфет в подарке, соответствующем условию задачи;
  • максимальное количество конфет с $$$f_i = 1$$$ в подарке с максимально возможным количеством конфет.
Пример
Входные данные
3
8
1 0
4 1
2 0
4 1
5 1
6 1
3 0
2 0
4
1 1
1 1
2 1
2 1
9
2 0
2 0
4 1
4 1
4 1
7 0
7 1
7 0
7 1
Выходные данные
3 3
3 3
9 5
Примечание

В первом запросе можно собрать подарок из двух конфет типа $$$4$$$ и одной конфеты типа $$$5$$$. У всех этих конфет $$$f_i = 1$$$.