Podczas przygotowywania danych do zadania D: ㄷㄷㄷㅈ, autorzy zadań UCPC odkryli, że tworzenie drzewa DUDUDUNGA o dużej liczbie wierzchołków jest trudne. Mając dane $N$, napisz program, który wypisze drzewo DUDUDUNGA o $N$ wierzchołkach.

Wejście

W pierwszej linii podana jest liczba wierzchołków drzewa $N$. ($6 \le N \le 300\,000$)

Wyjście

Wypisz $N-1$ linii, z których każda zawiera końce krawędzi oddzielone spacją. Numery wierzchołków muszą być liczbami całkowitymi z zakresu od $1$ do $N$.

Przykład

Wejście 1

6

Wyjście 1

1 2
2 3
3 4
4 5
4 6

Uwagi

Definicję drzewa DUDUDUNGA można znaleźć w zadaniu D: ㄷㄷㄷㅈ. Dla każdego podanego na wejściu $N$ zawsze istnieje drzewo DUDUDUNGA o $N$ wierzchołkach.