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

Вы и Нина играете в карточную игру. Для игры используется колода из $$$2n$$$ карт. На каждой карте написано целое число от $$$1$$$ до $$$n$$$, и каждое из чисел от $$$1$$$ до $$$n$$$ встречается ровно на $$$2$$$ картах. Кроме того, есть стол, на который размещаются карты во время игры (в начале игры стол пустой).

В начале игры эти $$$2n$$$ карты распределяются между вами и Ниной так, что каждый игрок получает по $$$n$$$ карт.

После этого вы и Нина поочередно делаете суммарно $$$2n$$$ ходов, т. е. каждый делает по $$$n$$$ ходов, начиная с вас. На каждом ходу:

  • Игрок, чей сейчас ход, выбирает одну из карт в своей руке. Пусть $$$x$$$ — число на выбранной карте.
  • Игрок, чей сейчас ход, получает $$$1$$$ очко, если на столе уже есть карта с числом $$$x$$$ (в противном случае он не получает очков). Затем он кладет выбранную карту с числом $$$x$$$ на стол.

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

Нина очень умная, поэтому она всегда выбирает карты оптимальным образом, чтобы максимизировать свой счет в конце игры (после $$$2n$$$ раундов). Если у нее есть несколько оптимальных ходов, она выбирает ход, который минимизирует ваш счет в конце игры.

Более формально, Нина всегда делает ходы оптимальным образом, чтобы в первую очередь максимизировать свой счет в конце игры и во вторую очередь минимизировать ваш счет в конце игры.

Пусть в начале игры числа на ваших картах — $$$a_1, a_2, \ldots, a_n$$$. Какое максимальное количество очков вы можете получить, делая свои ходы оптимальным образом?

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

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

В первой строке дано одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — количество карт, которые вы и Нина получаете в начале игры.

Во второй строке даны $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — числа на картах в вашей руке. Гарантируется, что каждое целое число от $$$1$$$ до $$$n$$$ встречается в последовательности $$$a_1, a_2, \ldots, a_n$$$ не более $$$2$$$ раз.

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

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

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

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

В первом наборе входных данных на ваших картах написаны числа $$$1$$$, $$$1$$$, $$$2$$$ и $$$3$$$. На картах Нины написаны числа $$$2$$$, $$$3$$$, $$$4$$$ и $$$4$$$. Возможный ход игры:

  1. Вы выбираете одну из карт с числом $$$1$$$ и кладете ее на стол.
  2. Нина выбирает одну из карт с числом $$$4$$$ и кладет ее на стол.
  3. Вы выбираете карту с числом $$$1$$$, получаете $$$1$$$ очко и кладете выбранную карту на стол.
  4. Нина выбирает карту с числом $$$4$$$, получает $$$1$$$ очко и кладет выбранную карту на стол.
  5. Вы выбираете карту с числом $$$2$$$ и кладете ее на стол.
  6. Нина выбирает карту с числом $$$2$$$, получает $$$1$$$ очко и кладет выбранную карту на стол.
  7. Вы выбираете карту с числом $$$3$$$ и кладете ее на стол.
  8. Нина выбирает карту с числом $$$3$$$, получает $$$1$$$ очко и кладет выбранную карту на стол.

В конце игры вы набрали $$$1$$$ очко, а Нина $$$3$$$. Можно показать, что вы не можете набрать больше $$$1$$$ очка, если Нина играет оптимальным образом, поэтому ответ $$$1$$$.

Во втором тестовом случае, если оба игрока играют оптимальным образом, вы набираете $$$2$$$ очка, а Нина — $$$6$$$ очков.