Les organisateurs de l'UCPC ont découvert, lors de la création des données pour le problème D : ㄷㄷㄷㅈ, qu'il est difficile de construire un arbre DUDUDUNGA avec un grand nombre de sommets. Étant donné $N$, écrivons un programme qui affiche un arbre DUDUDUNGA possédant $N$ sommets.

Entrée

La première ligne contient le nombre de sommets $N$ de l'arbre. ($6 \le N \le 300\,000$)

Sortie

Affichez $N-1$ lignes contenant les deux extrémités de chaque arête, séparées par un espace. Les numéros des sommets doivent être des entiers compris entre $1$ et $N$.

Exemples

Entrée 1

6

Sortie 1

1 2
2 3
3 4
4 5
4 6

Remarque

Pour la définition de l'arbre DUDUDUNGA, veuillez vous référer au problème D : ㄷㄷㄷㅈ. Pour tout $N$ donné en entrée, il existe toujours un arbre DUDUDUNGA possédant $N$ sommets.