A los trilobites les encanta construir metros. Ha diseñado $n$ líneas, cada una con $n+1$ posibles ubicaciones de estaciones, representadas por coordenadas en un plano.

Para enriquecer la experiencia del metro, el trilobite ha decidido que cada línea sea un segmento de recta. Es decir, para cada línea, el trilobite solo elegirá dos estaciones y conectará un segmento entre ellas. Para maximizar la dificultad de los transbordos de los pasajeros, el trilobite requiere que el número de intersecciones entre las $n$ líneas de metro construidas sea mínimo. Ten en cuenta que las intersecciones incluyen los puntos de inicio y fin. Por favor, planifica una solución válida.

En términos sencillos: se dan $n$ colores de puntos en un plano bidimensional, con $n+1$ puntos para cada color. Se requiere elegir dos puntos distintos de cada color para conectar un segmento de recta, de modo que el número total de intersecciones entre los $n$ segmentos sea mínimo. Genera una solución válida.

Nota: Si dos segmentos son colineales, el número de intersecciones se define como infinito. Todos los infinitos se consideran iguales.

Entrada

Este problema contiene múltiples casos de prueba. La primera línea contiene un entero positivo $T$ que indica el número de casos de prueba. Para cada caso de prueba:

La primera línea contiene un entero positivo $n$, el número de líneas.

Las siguientes $n$ líneas contienen cada una $2n+2$ enteros, donde el $(2i-1)$-ésimo y el $(2i)$-ésimo entero $(x_i, y_i)$ identifican las coordenadas de una estación de la línea actual, y el índice de dicha estación es $i$.

Se garantiza que todas las coordenadas de las estaciones son distintas.

Salida

Para cada caso de prueba, imprime $n$ líneas, cada una con dos enteros positivos, que indiquen los índices de las dos estaciones conectadas por cada línea, respectivamente. Solo necesitas imprimir una solución válida.

Ejemplos

Entrada 1

1
2
5 0 0 8 10 8
0 4 10 4 5 12

Salida 1

1 3
1 3

Nota

En la figura, los puntos azules y rojos representan las estaciones de la línea uno y la línea dos, respectivamente, y las líneas azul y roja representan los segmentos elegidos para la línea uno y la línea dos.

Ten en cuenta que solo necesitas imprimir una solución válida, por lo que:

1 2
2 3

también es una respuesta correcta.

Restricciones

Para todos los datos: $1\le n\le 1000, \sum n\leq 2000$, $|x_i|, |y_i|\le 10^9$.