Hay un país próspero llamado AA, formado por $n$ ciudades (numeradas del $1$ al $n$) y $n-1$ carreteras. Gracias al buen diseño de las carreteras, puedes salir de cualquier ciudad y recorrer varias carreteras para llegar al destino que desees.

El rey de AA, Dreamoon, quería inspeccionar mañana el orden y la seguridad de todas las ciudades, por lo que preparó una ruta: un camino de $2\times n-2$ aristas que empieza y termina en la ciudad $1$ (la capital de AA). Para facilitar el registro, Dreamoon escribe en un papel, en orden, los números de las ciudades de ese camino.

Sin embargo, Dreamoon derramó por desgracia té con leche sobre el papel, y ahora varios números consecutivos no se ven bien. Por eso te pide que ayudes a restaurarlos para poder tener un buen viaje.

Si hay varias soluciones, muestra la menor en orden lexicográfico. Además, se garantiza que hay al menos una solución para la entrada dada.

Entrada

La primera línea contiene un entero $T$, el número de casos de prueba. A continuación se describen los conjuntos de datos de entrada.

Cada caso de prueba tiene dos líneas. La primera contiene un entero $n$, el número de ciudades de AA. La segunda contiene $2\times n-1$ enteros entre $0$ y $n$; el número $i$ representa la ciudad $i$ del camino. Si ese número es $0$, significa que no se puede leer bien por el té con leche derramado. Se garantiza que todos los ceros son consecutivos y que hay al menos un cero.

Restricciones

• $1\le T\le30\,000$.

• $1\le n\le300\,000$.

• Las ciudades están numeradas del $1$ al $n$.

• Al menos uno de los números de ciudad escritos por Dreamoon en el papel no se ve bien, y todos los números ilegibles son consecutivos.

• La suma de $n$ de todos los casos de prueba no supera $300\,000$.

Salida

Para cada caso de prueba, muestra una línea con $2\times n-1$ números entre $1$ y $n$, que representen el camino restaurado. Recuerda mostrar la menor solución en orden lexicográfico si hay varias. Se garantiza que hay al menos una solución para la entrada dada.

Ejemplos

Entrada 1

9
5
1 2 3 2 0 2 1 5 1
5
1 2 3 0 0 2 1 5 1
5
1 2 0 0 0 2 1 5 1
5
1 2 0 0 0 0 1 5 1
5
1 0 0 0 0 0 1 5 1
5
1 0 0 0 0 0 0 5 1
5
1 0 0 0 0 0 0 0 1
5
1 0 0 0 0 0 0 0 0
5
0 0 0 0 0 0 0 0 0

Salida 1

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