あなたとNeneはカードゲームをしています。このゲームでは、$2n$ 枚のカードからなるデッキを使用します。各カードには $1$ から $n$ までの整数が書かれており、各整数 $1$ から $n$ はちょうど $2$ 枚のカードに書かれています。また、ゲーム中にカードを置くためのテーブルがあります（最初はテーブルは空です）。

ゲームの開始時に、$2n$ 枚のカードはあなたとNeneに $n$ 枚ずつ配られます。

その後、あなたとNeneは交互に合計 $2n$ 回のターンを行います。つまり、各プレイヤーが $n$ 回ずつターンを行います。先攻はあなたです。各ターンにおいて：

• ターンプレイヤーは自分の手札からカードを1枚選びます。そのカードに書かれた数を $x$ とします。
• テーブル上にすでに数 $x$ が書かれたカードがある場合、ターンプレイヤーは $1$ 点を獲得します（そうでない場合、得点は入りません）。その後、選んだ数 $x$ のカードをテーブルに置きます。

ターンは公開で行われます。各プレイヤーは常にテーブル上のすべてのカードを見ることができます。

Neneは非常に賢く、ゲーム終了時（$2n$ ターン終了後）の自分のスコアを最大化するように常に最適にカードを選びます。もし最適な選択肢が複数ある場合、彼女はゲーム終了時のあなたのスコアを最小化するような選択をします。

より厳密に言えば、Neneは常に、第一に自分の最終スコアを最大化し、第二にあなたの最終スコアを最小化するように最適にターンを行います。

カードがすでに配られ、あなたの手札にあるカードの数が $a_1, a_2, \ldots, a_n$ であると仮定したとき、あなたが最適にターンを行った場合に獲得できる最大得点はいくつでしょうか。

入力

各テストケースには複数のテストケースが含まれます。最初の行にはテストケースの数 $t$ ($1 \le t \le 10^4$) が含まれます。続いて各テストケースの説明が続きます。

各テストケースの最初の行には、ゲーム開始時にあなたとNeneが受け取るカードの枚数 $n$ ($1 \le n \le 2 \cdot 10^5$) が含まれます。

2行目には、あなたの手札にあるカードの数 $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$ を超えないことが保証されています。

出力

各テストケースについて、あなたが獲得できる最大得点を1つの整数で出力してください。

入出力例

入力 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$ が書かれたカードを1枚選び、テーブルに置きます。
2. Neneは $4$ が書かれたカードを1枚選び、テーブルに置きます。
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番目のテストケースでは、両者が最適にプレイした場合、あなたは $2$ 点を獲得し、Neneは $6$ 点を獲得します。