Alice y Bob tienen $2n$ cartas, cada una con un entero escrito en ella, de modo que cada entero entre $1$ y $n$ aparece en exactamente dos cartas. Inicialmente, Alice y Bob tienen $n$ cartas cada uno.

Van a jugar a un juego de cartas, comenzando Alice. En cada turno, el jugador actual coloca una carta de su mano en la parte superior de la pila. Si ahora hay dos cartas con el mismo número en la pila, el jugador actual anota $1$ punto y retira las dos cartas iguales junto con todas las cartas intermedias, colocándolas en la pila de descartes.

Dada la secuencia de jugadas de Alice, ¿cómo puede Bob organizar sus jugadas para minimizar la puntuación de Alice?

Entrada

La primera línea contiene un entero $T$ ($1 \le T \le 10^5$), que indica el número de casos de prueba.

Para cada caso de prueba, la primera línea contiene un entero $n$ ($1 \le n \le 5 \times 10^5$).

La segunda línea contiene $n$ enteros $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$), que representan en orden los números de las cartas jugadas por Alice. Se garantiza que ningún número aparece más de dos veces en $a_i$.

Se garantiza que la suma de $n$ en todos los casos de prueba no supera $5 \times 10^5$.

Salida

Para cada caso de prueba, la primera línea de salida debe contener un entero, que representa la puntuación mínima que puede obtener Alice.

La segunda línea debe contener $n$ enteros $b_1, b_2, \dots, b_n$ ($1 \le b_i \le n$), que representan las jugadas de Bob en orden, de modo que cada entero de $1$ a $n$ aparezca exactamente dos veces en las secuencias combinadas de $a_i$ y $b_i$.

Ejemplo

Entrada

3
3
1 2 3
5
3 1 4 1 5
5
1 4 5 1 4

Salida

0
1 2 3
0
2 3 2 4 5
1
3 2 2 3 5

Nota

Para el tercer caso de prueba, el juego transcurre de la siguiente manera: