你和 Nene 正在玩纸牌游戏。玩这个游戏需要使用带有 $$$2n$$$ 卡的牌组。每张卡片上都有一个从 $$$1$$$ 到 $$$n$$$ 的整数,并且每个整数 $$$1$$$ 到 $$$n$$$ 都准确地出现在 $$$2$$$ 卡片上。此外,还有一张桌子,用于在游戏过程中放置纸牌(最初,桌子是空的)。
在游戏开始时,这些 $$$2n$$$ 卡牌会在你和 Nene 之间分发,这样每个玩家都会收到 $$$n$$$ 卡牌。
之后,你和 Nene 轮流进行 $$$2n$$$ 轮,即每个人从你开始轮流 $$$n$$$。每回合:
- 轮到的玩家选择他手中的一张牌。令 $$$x$$$ 为上面的数字。
- 如果桌上已经有一张带有整数 $$$x$$$ 的牌,则轮到的玩家将获得 $$$1$$$ 点(否则,他不会获得任何点)。之后,他将所选的带有整数 $$$x$$$ 的卡片放在桌子上。
请注意,回合是公开进行的:每个玩家每时每刻都可以看到桌上的所有牌。
Nene 非常聪明,所以她总是选择最佳的牌,以便在游戏结束时(在 $$$2n$$$ 轮之后)最大化她的分数。如果她有几个最佳动作,她会选择在游戏结束时使你的分数最小化的动作。
更正式地说,Nene 总是以最佳方式轮流,以便首先在游戏结束时最大化她的得分,然后在游戏结束时最小化你的得分。
假设卡片已经分发完毕,并且你手中的卡片上写有整数$$$a_1,a_2,\ldots,a_n$$$,那么你最优轮流最多可以获得多少分?
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 您和 Nene 在游戏开始时收到的牌数。
第二行包含 $$$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$$$。 Nene 卡片上写的整数是 $$$2$$$、$$$3$$$、$$$4$$$ 和 $$$4$$$。游戏可能会按如下方式进行:
1. 您选择一张写有整数 $$$1$$$ 的卡片并将其放在桌子上。
2. Nene 选择一张写有整数 $$$4$$$ 的卡片并将其放在桌子上。
3. 您选择写有整数 $$$1$$$ 的卡片,获得 $$$1$$$ 积分,并将所选卡片放在桌子上。
4. Nene 选择写有整数 $$$4$$$ 的卡片,获得 $$$1$$$ 点,并将所选卡片放在桌子上。
5. 选择写有整数 $$$2$$$ 的卡片并将其放在桌子上。
6. Nene 选择上面写有整数 $$$2$$$ 的卡片,获得 $$$1$$$ 点,并将所选卡片放在桌子上。
7. 选择写有整数 $$$3$$$ 的卡片并将其放在桌子上。
8. Nene 选择写有整数 $$$3$$$ 的卡片,获得 $$$1$$$ 点,并将所选卡片放在桌子上。
游戏结束时,您获得了 $$$1$$$ 分,Nene 获得了 $$$3$$$ 分。可以证明,如果 Nene 发挥最佳,您的得分不会超过 $$$1$$$ 分,因此答案是 $$$1$$$。
在第二个测试用例中,如果两名玩家都发挥最佳,您将获得 $$$2$$$ 分,Nene 将获得 $$$6$$$ 分。