CF 1956B - Nene and the Card Game

你和 Nene 正在玩纸牌游戏。 玩这个游戏使用的是有 2n 张牌的牌组。 每张卡片上都有一个从 1 到 n 的整数，并且整数 1 到 n 中的每一个都恰好出现在 2 张卡片上。 此外，还有一张桌子，用于在游戏过程中放置纸牌（最初，桌子是空的）。

游戏开始时，这 2n 张牌会在你和 Nene 之间分发，这样每个玩家都会收到 n 张牌。

之后，你和 Nene 交替进行 2n 轮，即每个人从你开始进行 n 轮。 每回合：

轮到的玩家选择他手中的一张牌。 设 x 为上面的数字。

如果桌上已经有一张带有整数 x 的牌，则轮到该玩家的玩家将获得 1 分（否则，他不会获得任何分数）。 之后，他将所选的带有整数 x 的卡片放在桌子上。

请注意，回合是公开进行的：每个玩家都可以随时看到桌上的所有牌。

Nene 非常聪明，所以她总是选择最佳的牌，以便在游戏结束时（2n 轮后）最大化她的分数。 如果她有几个最佳动作，她会选择在游戏结束时使你的分数最小化的动作。

更正式地说，内内总是以最佳方式轮流，以便首先在游戏结束时最大化她的得分，然后在游戏结束时最小化你的得分。

假设牌已经分发完毕，你手中的牌上写着整数a1,a2,…,an，那么你最优轮流最多可以获得多少分？

输入

每个测试包含多个测试用例。 第一行包含测试用例的数量 t (1≤t≤104)。 测试用例的描述如下。

第一行包含一个整数 n (1≤n≤2⋅105) — 您和 Nene 在游戏开始时收到的牌数。

第二行包含n个整数a1,a2,…,an (1≤ai≤n)——你手中牌上的整数。 保证从 1 到 n 的每个整数在序列 a1,a2,…,an 中最多出现 2 次。

保证所有测试用例的 n 之和不超过 2⋅105。

输出

对于每个测试用例，输出一个整数：可以获得的最大分数。

nene有后手优势,所以只能选择自己有重复数字的卡出, 有多少对重复的卡,最终的得分就是多少, 剩下的肯定都是nene得分的.