Para un entero positivo $n$, una secuencia de longitud $n$ se llama «secuencia de ladrillos rojos» si cumple las siguientes condiciones:

• Cada uno de los números $1, 2, \ldots, n$ aparece exactamente una vez en la secuencia.
• La suma de cada par de elementos adyacentes no es un cuadrado perfecto.

Dado un entero $n$, construye una secuencia de ladrillos rojos de longitud $n$.

Entrada

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

Para cada caso de prueba, la única línea contiene un entero $n$ ($1 \le n \le 4 \times 10^6$), la longitud requerida de la secuencia de ladrillos rojos.

Se garantiza que la suma de $n$ no supera $4 \times 10^6$. Se puede demostrar que siempre existe una solución bajo las restricciones dadas.

Salida

Imprime $T$ líneas, cada una con la secuencia que se debe construir. Si hay múltiples respuestas, imprime cualquiera de ellas.

Ejemplos

Entrada 1

5
1
2
3
4
5

Salida 1

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

Nota

Para $n = 5$, si la secuencia de salida es 1 2 3 4 5, es una respuesta incorrecta porque $4 + 5 = 9$ es un cuadrado perfecto.