당신과 네네는 카드 게임을 하고 있습니다. 이 게임에는 $2n$장의 카드가 사용됩니다. 각 카드에는 $1$부터 $n$까지의 정수가 적혀 있으며, $1$부터 $n$까지의 각 정수는 정확히 $2$장의 카드에 적혀 있습니다. 또한, 게임 중에 카드를 놓을 수 있는 테이블이 있습니다(처음에는 테이블이 비어 있습니다).

게임 시작 시, $2n$장의 카드는 당신과 네네에게 각각 $n$장씩 분배됩니다.

그 후, 당신과 네네는 번갈아 가며 총 $2n$번의 턴을 진행합니다. 즉, 각자 $n$번씩 턴을 가지며, 당신이 먼저 시작합니다. 각 턴마다 다음이 수행됩니다:

• 현재 턴인 플레이어는 자신의 손에 있는 카드 중 하나를 선택합니다. 선택한 카드에 적힌 숫자를 $x$라고 합시다.
• 테이블에 이미 숫자 $x$가 적힌 카드가 있다면, 현재 턴인 플레이어는 $1$점을 얻습니다(그렇지 않으면 점수를 얻지 못합니다). 그 후, 선택한 숫자 $x$가 적힌 카드를 테이블에 놓습니다.

턴은 공개적으로 진행됩니다. 즉, 각 플레이어는 매 순간 테이블에 놓인 모든 카드를 볼 수 있습니다.

네네는 매우 똑똑해서 게임 종료 시(총 $2n$번의 턴 후) 자신의 점수를 최대화하기 위해 항상 최적으로 카드를 선택합니다. 만약 최적의 수가 여러 개라면, 게임 종료 시 당신의 점수를 최소화하는 수를 선택합니다.

더 공식적으로 말하자면, 네네는 우선 자신의 점수를 최대화하고, 그다음으로 당신의 점수를 최소화하는 방향으로 항상 최적으로 턴을 진행합니다.

카드가 이미 분배되어 있고 당신의 손에 있는 카드에 적힌 정수가 $a_1, a_2, \ldots, a_n$이라고 할 때, 당신이 최적으로 턴을 진행하여 얻을 수 있는 최대 점수는 얼마입니까?

입력

각 테스트 케이스는 여러 개의 테스트 케이스를 포함합니다. 첫 번째 줄에는 테스트 케이스의 수 $t$ ($1 \le t \le 10^4$)가 주어집니다. 각 테스트 케이스에 대한 설명은 다음과 같습니다.

첫 번째 줄에는 당신과 네네가 처음에 받는 카드의 수 $n$ ($1 \le n \le 2 \cdot 10^5$)이 주어집니다.

두 번째 줄에는 당신의 손에 있는 카드에 적힌 $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$입니다. 네네의 카드에 적힌 정수는 $2, 3, 4, 4$입니다. 게임은 다음과 같이 진행될 수 있습니다:

1. 당신이 숫자 $1$이 적힌 카드 중 하나를 선택하여 테이블에 놓습니다.
2. 네네가 숫자 $4$가 적힌 카드 중 하나를 선택하여 테이블에 놓습니다.
3. 당신이 숫자 $1$이 적힌 카드를 선택하여 $1$점을 얻고 테이블에 놓습니다.
4. 네네가 숫자 $4$가 적힌 카드를 선택하여 $1$점을 얻고 테이블에 놓습니다.
5. 당신이 숫자 $2$가 적힌 카드를 선택하여 테이블에 놓습니다.
6. 네네가 숫자 $2$가 적힌 카드를 선택하여 $1$점을 얻고 테이블에 놓습니다.
7. 당신이 숫자 $3$이 적힌 카드를 선택하여 테이블에 놓습니다.
8. 네네가 숫자 $3$이 적힌 카드를 선택하여 $1$점을 얻고 테이블에 놓습니다.

게임 종료 시 당신은 $1$점을 얻었고, 네네는 $3$점을 얻었습니다. 네네가 최적으로 플레이할 경우 당신은 $1$점보다 더 많은 점수를 얻을 수 없음을 보일 수 있으므로, 정답은 $1$입니다.

두 번째 테스트 케이스에서 두 플레이어 모두 최적으로 플레이한다면, 당신은 $2$점을 얻고 네네는 $6$점을 얻습니다.