B. Разделение
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дана последовательность $$$a$$$, содержащая $$$2n$$$ целых чисел. Обозначим как $$$f(b)$$$ количество различных элементов с нечётным числом вхождений в последовательность $$$b$$$. Вам необходимо разделить данный массив на две непересекающиеся подпоследовательности $$$p$$$ и $$$q$$$, каждая из которых имеет размер $$$n$$$, так чтобы $$$f(p) + f(q)$$$ было максимальным. Выведите максимальное значение.

Последовательность $$$a$$$ является подпоследовательностью $$$b$$$, если $$$a$$$ может быть получена из $$$b$$$ удалением нескольких (возможно, ни одного или всех) элементов на произвольных позициях.

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

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

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

Вторая строка содержит $$$2n$$$ целых чисел $$$a_1,a_2,\ldots,a_{2n}$$$ ($$$1 \le a_i \le 2n$$$) — элементы последовательности $$$a$$$.

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

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

Для каждого набора входных данных выведите одну строку.

Вы должны вывести максимальное значение $$$f(p) + f(q)$$$, которое можно достичь.

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

Для первого набора входных данных:

  • Мы можем разделить массив так, чтобы $$$p = [1, 3]$$$ и $$$q = [2, 4]$$$.
  • Таким образом, $$$f(p) = 2$$$ и $$$f(q) = 2$$$, так как в обеих последовательностях два различных элемента с нечётным числом вхождений.

Для второго набора входных данных:

  • Мы можем разделить массив так, чтобы $$$p = [5, 5, 5]$$$ и $$$q = [5, 5, 5]$$$.
  • Таким образом, $$$f(p) = 1$$$ и $$$f(q) = 1$$$.

Для пятого набора входных данных:

  • Мы можем разделить массив так, чтобы $$$p = [1, 2, 3, 4, 5, 6]$$$ и $$$q = [4, 1, 4, 1, 5, 4]$$$.
  • Таким образом, $$$f(p) = 6$$$ и $$$f(q) = 2$$$.