Tú y Nene están jugando un juego de cartas. Se utiliza una baraja con $2n$ cartas para jugar este juego. Cada carta tiene un número entero del $1$ al $n$, y cada uno de los números enteros del $1$ al $n$ aparece exactamente en $2$ cartas. Además, hay una mesa donde se colocan las cartas durante el juego (inicialmente, la mesa está vacía).

Al comienzo del juego, estas $2n$ cartas se distribuyen entre tú y Nene de modo que cada jugador recibe $n$ cartas.

Después de esto, tú y Nene toman turnos alternativamente $2n$ veces, es decir, cada persona toma $n$ turnos, comenzando contigo. En cada turno:

• El jugador cuyo turno es selecciona una de las cartas de su mano. Sea $x$ el número en ella.
• El jugador cuyo turno es recibe $1$ punto si ya hay una carta con el número entero $x$ en la mesa (de lo contrario, no recibe puntos). Después de esto, coloca la carta seleccionada con el número entero $x$ en la mesa.

Ten en cuenta que los turnos se realizan públicamente: cada jugador puede ver todas las cartas en la mesa en cada momento.

Nene es muy inteligente, por lo que siempre selecciona las cartas de manera óptima para maximizar su puntuación al final del juego (después de $2n$ rondas). Si tiene varios movimientos óptimos, selecciona el movimiento que minimiza tu puntuación al final del juego.

Más formalmente, Nene siempre toma turnos de manera óptima para maximizar su puntuación al final del juego en primer lugar y para minimizar tu puntuación al final del juego en segundo lugar.

Suponiendo que las cartas ya están distribuidas y las cartas en tu mano tienen los números enteros $a_1, a_2, \ldots, a_n$ escritos en ellas, ¿cuál es el número máximo de puntos que puedes obtener tomando tus turnos de manera óptima?

Entrada

Cada prueba contiene múltiples casos de prueba. La primera línea contiene el número de casos de prueba $t$ ($1 \le t \le 10^4$). A continuación se describe cada caso de prueba.

La primera línea contiene un solo número entero $n$ ($1 \le n \le 2 \cdot 10^5$), el número de cartas que tú y Nene reciben al comienzo del juego.

La segunda línea contiene $n$ números enteros $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$), los números enteros en las cartas de tu mano. Se garantiza que cada número entero del $1$ al $n$ aparece en la secuencia $a_1, a_2, \ldots, a_n$ como máximo $2$ veces.

Se garantiza que la suma de $n$ sobre todos los casos de prueba no excede $2 \cdot 10^5$.

Salida

Para cada caso de prueba, imprime un número entero: el número máximo de puntos que puedes obtener.

Ejemplos

Entrada 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

Salida 1

1
2
1
0
0

Nota

En el primer caso de prueba, los números enteros escritos en tus cartas son $1$, $1$, $2$ y $3$. Los números enteros escritos en las cartas de Nene son $2$, $3$, $4$ y $4$. El juego puede proceder de la siguiente manera:

1. Seleccionas una de las cartas con el número entero $1$ escrito en ella y la colocas sobre la mesa.
2. Nene selecciona una de las cartas con el número entero $4$ escrito en ella y la coloca sobre la mesa.
3. Seleccionas la carta con el número entero $1$ escrito en ella, recibes $1$ punto y colocas la carta seleccionada sobre la mesa.
4. Nene selecciona la carta con el número entero $4$ escrito en ella, recibe $1$ punto y coloca la carta seleccionada sobre la mesa.
5. Seleccionas la carta con el número entero $2$ escrito en ella y la colocas sobre la mesa.
6. Nene selecciona la carta con el número entero $2$ escrito en ella, recibe $1$ punto y coloca la carta seleccionada sobre la mesa.
7. Seleccionas la carta con el número entero $3$ escrito en ella y la colocas sobre la mesa.
8. Nene selecciona la carta con el número entero $3$ escrito en ella, recibe $1$ punto y coloca la carta seleccionada sobre la mesa.

Al final del juego, tú obtuviste $1$ punto y Nene obtuvo $3$. Se puede demostrar que no puedes obtener más de $1$ punto si Nene juega de manera óptima, por lo que la respuesta es $1$.

En el segundo caso de prueba, si ambos jugadores juegan de manera óptima, tú obtienes $2$ puntos y Nene obtiene $6$ puntos.