Bạn và Nene đang chơi một trò chơi bài. Bộ bài gồm $2n$ lá được sử dụng để chơi trò này. Mỗi lá bài có một số nguyên từ $1$ đến $n$, và mỗi số nguyên từ $1$ đến $n$ xuất hiện chính xác trên $2$ lá bài. Ngoài ra, có một cái bàn nơi các lá bài được đặt lên trong suốt trò chơi (ban đầu, bàn trống).

Khi bắt đầu trò chơi, $2n$ lá bài này được chia cho bạn và Nene sao cho mỗi người nhận được $n$ lá bài.

Sau đó, bạn và Nene luân phiên thực hiện $2n$ lượt, nghĩa là mỗi người thực hiện $n$ lượt, bắt đầu với bạn. Trong mỗi lượt:

• Người chơi đến lượt chọn một trong các lá bài trên tay mình. Gọi $x$ là số trên lá bài đó.
• Người chơi đến lượt nhận được $1$ điểm nếu đã có một lá bài mang số $x$ trên bàn (nếu không, họ không nhận được điểm nào). Sau đó, họ đặt lá bài mang số $x$ đã chọn lên bàn.

Lưu ý rằng các lượt chơi được thực hiện công khai: mỗi người chơi có thể nhìn thấy tất cả các lá bài trên bàn tại mọi thời điểm.

Nene rất thông minh nên cô ấy luôn chọn bài một cách tối ưu để tối đa hóa điểm số của mình khi kết thúc trò chơi (sau $2n$ vòng). Nếu cô ấy có nhiều nước đi tối ưu, cô ấy sẽ chọn nước đi giúp tối thiểu hóa điểm số của bạn khi kết thúc trò chơi.

Nói một cách chính thức hơn, Nene luôn thực hiện các lượt chơi một cách tối ưu để trước hết tối đa hóa điểm số của mình và sau đó là tối thiểu hóa điểm số của bạn khi kết thúc trò chơi.

Giả sử các lá bài đã được chia và các lá bài trên tay bạn có các số nguyên $a_1, a_2, \ldots, a_n$, số điểm tối đa bạn có thể nhận được khi thực hiện các lượt chơi của mình một cách tối ưu là bao nhiêu?

Dữ liệu vào

Mỗi bài kiểm tra chứa nhiều trường hợp thử nghiệm. Dòng đầu tiên chứa số lượng trường hợp thử nghiệm $t$ ($1 \le t \le 10^4$). Tiếp theo là mô tả các trường hợp thử nghiệm.

Dòng đầu tiên chứa một số nguyên duy nhất $n$ ($1 \le n \le 2 \cdot 10^5$) --- số lượng lá bài bạn và Nene nhận được khi bắt đầu trò chơi.

Dòng thứ hai chứa $n$ số nguyên $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$) --- các số nguyên trên các lá bài trên tay bạn. Đảm bảo rằng mỗi số nguyên từ $1$ đến $n$ xuất hiện trong dãy $a_1, a_2, \ldots, a_n$ tối đa $2$ lần.

Đảm bảo rằng tổng của $n$ trên tất cả các trường hợp thử nghiệm không vượt quá $2 \cdot 10^5$.

Dữ liệu ra

Với mỗi trường hợp thử nghiệm, hãy in ra một số nguyên: số điểm tối đa bạn có thể nhận được.

Ví dụ

Ví dụ 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

Kết quả 1

1
2
1
0
0

Ghi chú

Trong trường hợp thử nghiệm đầu tiên, các số nguyên trên bài của bạn là $1$, $1$, $2$ và $3$. Các số nguyên trên bài của Nene là $2$, $3$, $4$ và $4$. Trò chơi có thể diễn ra như sau:

1. Bạn chọn một trong các lá bài mang số $1$ và đặt lên bàn.
2. Nene chọn một trong các lá bài mang số $4$ và đặt lên bàn.
3. Bạn chọn lá bài mang số $1$ còn lại, nhận $1$ điểm và đặt lá bài đó lên bàn.
4. Nene chọn lá bài mang số $4$ còn lại, nhận $1$ điểm và đặt lá bài đó lên bàn.
5. Bạn chọn lá bài mang số $2$ và đặt lên bàn.
6. Nene chọn lá bài mang số $2$ còn lại, nhận $1$ điểm và đặt lá bài đó lên bàn.
7. Bạn chọn lá bài mang số $3$ và đặt lên bàn.
8. Nene chọn lá bài mang số $3$ còn lại, nhận $1$ điểm và đặt lá bài đó lên bàn.

Khi kết thúc trò chơi, bạn ghi được $1$ điểm, và Nene ghi được $3$ điểm. Có thể chứng minh rằng bạn không thể ghi được nhiều hơn $1$ điểm nếu Nene chơi tối ưu, vì vậy câu trả lời là $1$.

Trong trường hợp thử nghiệm thứ hai, nếu cả hai người chơi đều chơi tối ưu, bạn ghi được $2$ điểm và Nene ghi được $6$ điểm.