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

Алиса только что создала схему с $$$n$$$ лампочками и $$$2n$$$ переключателями. Каждый компонент (лампочка или переключатель) имеет два состояния: включен или выключен. Лампочки и переключатели расположены таким образом:

  • Каждая лампочка подключена к ровно двум переключателям.
  • Каждый переключатель подключен к ровно одной лампочке. Неизвестно, к какой лампочке подключен каждый переключатель.
  • Когда все переключатели выключены, все лампочки также выключены.
  • Если переключатель переключается (с включенного на выключенный или наоборот), состояние лампочки, к которой он подключен, также переключается.

Алиса принесла схему, которая показывает только состояния $$$2n$$$ переключателей, своей сестре Ирис и задала ей загадку: каково минимальное и максимальное количество лампочек, которые могут быть включены?

Зная проделки своей младшей сестры слишком хорошо, Ирис не тратит больше секунды, чтобы дать Алисе правильный ответ. Можете ли вы сделать также?

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

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 500$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 50$$$) — количество лампочек в схеме.

Вторая строка каждого набора входных данных содержит $$$2n$$$ целых чисел $$$a_1, a_2, \ldots, a_{2n}$$$ ($$$0 \le a_i \le 1$$$) — состояния переключателей в схеме. $$$a_i = 0$$$ означает, что $$$i$$$-й переключатель выключен, а $$$a_i = 1$$$ означает, что $$$i$$$-й переключатель включен.

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

Для каждого набора входных данных выведите два целых числа — минимальное и максимальное количество лампочек, которые могут быть включены, соответственно.

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

В первом наборе входных данных в схеме только одна лампочка, и ни один переключатель не включен, поэтому лампочка точно выключена.

Во втором наборе входных данных в схеме только одна лампочка, но один переключатель, подключенный к ней, включен, поэтому лампочка включена.

В третьем наборе входных данных в схеме только одна лампочка, оба переключателя включены, поэтому лампочка выключена, так как переключается дважды.

В четвёртом наборе входных данных, чтобы не было включенных лампочек, переключатели могут быть расположены следующим образом:

  • Переключатель $$$1$$$ и переключатель $$$4$$$ подключены к лампочке $$$1$$$. Поскольку оба переключателя выключены, лампочка $$$1$$$ также выключена.
  • Переключатель $$$2$$$ и переключатель $$$6$$$ подключены к лампочке $$$2$$$. Поскольку оба переключателя выключены, лампочка $$$2$$$ также выключена.
  • Переключатель $$$3$$$ и переключатель $$$5$$$ подключены к лампочке $$$3$$$. Оба переключателя включены, поэтому лампочка $$$3$$$ переключается дважды из своего первоначального выключенного состояния и, следовательно, также остается выключенной.

А чтобы включить $$$2$$$ лампочки, переключатели могут быть расположены следующим образом:

  • Переключатель $$$1$$$ и переключатель $$$2$$$ подключены к лампочке $$$1$$$. Поскольку оба переключателя выключены, лампочка $$$1$$$ также выключена.
  • Переключатель $$$3$$$ и переключатель $$$4$$$ подключены к лампочке $$$2$$$. Поскольку переключатель $$$3$$$ включен, а переключатель $$$4$$$ выключен, лампочка $$$2$$$ переключается один раз из своего первоначального выключенного состояния, поэтому она включена.
  • Переключатель $$$5$$$ и переключатель $$$6$$$ подключены к лампочке $$$3$$$. Поскольку переключатель $$$5$$$ включен, а переключатель $$$6$$$ выключен, лампочка $$$3$$$ переключается один раз из своего первоначального выключенного состояния, поэтому она включена.