311250: CF1956B. Nene and the Card Game

B. Nene and the Card Gametime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

You and Nene are playing a card game. The deck with $2n$ cards is used to play this game. Each card has an integer from $1$ to $n$ on it, and each of integers $1$ through $n$ appears exactly on $2$ cards. Additionally, there is a table where cards are placed during the game (initially, the table is empty).

In the beginning of the game, these $2n$ cards are distributed between you and Nene so that each player receives $n$ cards.

After it, you and Nene alternatively take $2n$ turns, i.e. each person takes $n$ turns, starting with you. On each turn:

• The player whose turn is it selects one of the cards in his hand. Let $x$ be the number on it.
• The player whose turn is it receives $1$ point if there is already a card with the integer $x$ on the table (otherwise, he receives no points). After it, he places the selected card with the integer $x$ on the table.

Note that turns are made publicly: each player can see all the cards on the table at each moment.

Nene is very smart so she always selects cards optimally in order to maximize her score in the end of the game (after $2n$ rounds). If she has several optimal moves, she selects the move that minimizes your score in the end of the game.

More formally, Nene always takes turns optimally in order to maximize her score in the end of the game in the first place and to minimize your score in the end of the game in the second place.

Assuming that the cards are already distributed and cards in your hand have integers $a_1, a_2, \ldots, a_n$ written on them, what is the maximum number of points you can get by taking your turns optimally?

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of test cases follows.

The first line contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of cards you and Nene receive in the beginning of the game.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$) — the integers on the cards in your hand. It is guaranteed that each integer from $1$ through $n$ appears in the sequence $a_1, a_2, \ldots, a_n$ at most $2$ times.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

Output

For each test case, output one integer: the maximum number of points you can get.

ExampleInput

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

Output

1
2
1
0
0

Note

In the first test case, the integers written on your cards are $1$, $1$, $2$ and $3$. The integers written on Nene's cards are $2$, $3$, $4$ and $4$. The game may proceed as follows:

1. You select one of the cards with an integer $1$ written on it and place it on the table.
2. Nene selects one of the cards with an integer $4$ written on it and places it on the table.
3. You select the card with an integer $1$ written on it, receive $1$ point, and place the selected card on the table.
4. Nene selects the card with an integer $4$ written on it, receive $1$ point, and places the selected card on the table.
5. You select the card with an integer $2$ written on it and place it on the table.
6. Nene selects the card with an integer $2$ written on it, receive $1$ point, and places the selected card on the table.
7. You select the card with an integer $3$ written on it and place it on the table.
8. Nene selects the card with an integer $3$ written on it, receive $1$ point, and places the selected card on the table.

At the end of the game, you scored $1$ point, and Nene scored $3$. It can be shown that you cannot score more than $1$ point if Nene plays optimally, so the answer is $1$.

In the second test case, if both players play optimally, you score $2$ points and Nene scores $6$ points.

**B. Nene 和纸牌游戏**

**题目大意：**
你和 Nene 在玩一个纸牌游戏。游戏使用一副有 $2n$ 张牌的牌组，每张牌上有一个从 $1$ 到 $n$ 的整数，每个整数 $1$ 到 $n$ 都恰好出现在两张牌上。此外，有一张桌子用于在游戏中放置牌（最初，桌子上是空的）。

游戏开始时，这 $2n$ 张牌在你和 Nene 之间分配，每人得到 $n$ 张牌。之后，你和 Nene 交替进行 $2n$ 个回合，即每人进行 $n$ 个回合，从你开始。在每一回合中：

1. 当前玩家从手中选择一张牌。设 $x$ 为牌上的数字。
2. 如果桌上已经有一张数字为 $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$) —— 你手中的牌上的整数。保证序列 $a_1, a_2, \ldots, a_n$ 中每个整数从 $1$ 到 $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$。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$ 分。**B. Nene 和纸牌游戏** **题目大意：** 你和 Nene 在玩一个纸牌游戏。游戏使用一副有 $2n$ 张牌的牌组，每张牌上有一个从 $1$ 到 $n$ 的整数，每个整数 $1$ 到 $n$ 都恰好出现在两张牌上。此外，有一张桌子用于在游戏中放置牌（最初，桌子上是空的）。 游戏开始时，这 $2n$ 张牌在你和 Nene 之间分配，每人得到 $n$ 张牌。之后，你和 Nene 交替进行 $2n$ 个回合，即每人进行 $n$ 个回合，从你开始。在每一回合中： 1. 当前玩家从手中选择一张牌。设 $x$ 为牌上的数字。 2. 如果桌上已经有一张数字为 $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$) —— 你手中的牌上的整数。保证序列 $a_1, a_2, \ldots, a_n$ 中每个整数从 $1$ 到 $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$。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$ 分。