Mientras preparaban los datos para el problema D: ㄷㄷㄷㅈ, los autores de UCPC descubrieron que es difícil construir un árbol DUDUDUNGA con muchos vértices. Dado $N$, vamos a crear un programa que imprima un árbol DUDUDUNGA con $N$ vértices.

Entrada

En la primera línea se proporciona el número de vértices del árbol $N$. ($6 \le N \le 300\,000$)

Salida

Imprime $N-1$ líneas, cada una con los dos extremos de una arista separados por un espacio. Los números de los vértices deben ser enteros entre $1$ y $N$.

Ejemplos

Entrada 1

6

Salida 1

1 2
2 3
3 4
4 5
4 6

Nota

Para la definición del árbol DUDUDUNGA, consulta el problema D: ㄷㄷㄷㅈ. Para el $N$ dado en la entrada, siempre existe un árbol DUDUDUNGA con $N$ vértices.