Вы с Нене играете в карточную игру. Для игры используется колода из $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$.

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

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

Примеры

Примеры 1

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

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$ очков.